{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Erect the Fence"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #geometry #array #math"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #几何 #数组 #数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: outerTrees"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #安装栅栏"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个数组 <code>trees</code>，其中 <code>trees[i] = [x<sub>i</sub>, y<sub>i</sub>]</code> 表示树在花园中的位置。</p>\n",
    "\n",
    "<p>你被要求用最短长度的绳子把整个花园围起来，因为绳子很贵。只有把&nbsp;<strong>所有的树都围起来</strong>，花园才围得很好。</p>\n",
    "\n",
    "<p>返回<em>恰好位于围栏周边的树木的坐标</em>。</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2021/04/24/erect2-plane.jpg\" style=\"width: 400px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> points = [[1,1],[2,2],[2,0],[2,4],[3,3],[4,2]]\n",
    "<strong>输出:</strong> [[1,1],[2,0],[3,3],[2,4],[4,2]]</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2021/04/24/erect1-plane.jpg\" style=\"height: 393px; width: 400px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> points = [[1,2],[2,2],[4,2]]\n",
    "<strong>输出:</strong> [[4,2],[2,2],[1,2]]</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>注意:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= points.length &lt;= 3000</code></li>\n",
    "\t<li><code>points[i].length == 2</code></li>\n",
    "\t<li><code>0 &lt;= x<sub>i</sub>, y<sub>i</sub>&nbsp;&lt;= 100</code></li>\n",
    "\t<li>\n",
    "\t<p data-group=\"1-1\">所有给定的点都是&nbsp;<strong>唯一&nbsp;</strong>的。</p>\n",
    "\t</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [erect-the-fence](https://leetcode.cn/problems/erect-the-fence/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [erect-the-fence](https://leetcode.cn/problems/erect-the-fence/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,1],[2,2],[2,0],[2,4],[3,3],[4,2]]', '[[1,2],[2,2],[4,2]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def outerTrees(self, trees: List[List[int]]) -> List[float]:\n",
    "        def cover(x, y):\n",
    "            dis = sqrt((x-x0)**2 + (y-y0)**2)\n",
    "            return dis<=r or abs(dis-r)<10**(-6)\n",
    "\n",
    "        def cal(x1, y1, x2, y2, x3, y3):\n",
    "            a, b, c, d = x1-x2, y1-y2, x1-x3, y1-y3\n",
    "            a1 = (x1*x1-x2*x2+y1*y1-y2*y2)/2\n",
    "            a2 = (x1*x1-x3*x3+y1*y1-y3*y3)/2\n",
    "            theta = b*c-a*d\n",
    "            x0 = (b*a2-d*a1)/theta\n",
    "            y0 = (c*a1-a*a2)/theta\n",
    "            return x0, y0, sqrt((x1-x0)**2+(y1-y0)**2)\n",
    "\n",
    "        random.shuffle(trees)\n",
    "        n, (x0, y0), r = len(trees), trees[0], 0\n",
    "        for i in range(1, n):\n",
    "            x1, y1 = trees[i]\n",
    "            if cover(x1, y1):\n",
    "                continue\n",
    "            (x0, y0), r = trees[i], 0\n",
    "            for j in range(i):\n",
    "                x2, y2 = trees[j]\n",
    "                if cover(x2, y2):\n",
    "                    continue\n",
    "                x0, y0, r = (x1+x2)/2, (y1+y2)/2, sqrt((x2-x1)**2+(y2-y1)**2)/2\n",
    "                for k in range(j):\n",
    "                    x3, y3 = trees[k]\n",
    "                    if cover(x3, y3):\n",
    "                        continue\n",
    "                    x0, y0, r = cal(x1, y1, x2, y2, x3, y3)\n",
    "        return [x0, y0, r]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def outerTrees(self, trees: List[List[int]]) -> List[float]:\n",
    "        def cover(p):\n",
    "            return dist(p,p0)<=r+1e-6\n",
    "\n",
    "        def cal(p1, p2, p3):\n",
    "            (x1,y1),(x2,y2),(x3,y3) = p1,p2,p3\n",
    "            a, b, c, d = x1-x2, y1-y2, x1-x3, y1-y3\n",
    "            a1 = (x1*x1-x2*x2+y1*y1-y2*y2)/2\n",
    "            a2 = (x1*x1-x3*x3+y1*y1-y3*y3)/2\n",
    "            theta = b*c-a*d\n",
    "            x0 = (b*a2-d*a1)/theta\n",
    "            y0 = (c*a1-a*a2)/theta\n",
    "            p0 = [x0,y0]\n",
    "            return p0, dist(p1,p0)\n",
    "\n",
    "        T = trees\n",
    "        random.shuffle(T)\n",
    "        n, p0, r = len(T), T[0], 0\n",
    "        for i in range(1, n):\n",
    "            if cover(T[i]):\n",
    "                continue\n",
    "            p0, r = T[i], 0\n",
    "            for j in range(i):\n",
    "                if cover(T[j]):\n",
    "                    continue\n",
    "                p0, r = [(T[i][0]+T[j][0])/2, (T[i][1]+T[j][1])/2], dist(T[i],T[j])/2\n",
    "                for k in range(j):\n",
    "                    if cover(T[k]):\n",
    "                        continue\n",
    "                    p0, r = cal(T[i], T[j], T[k])\n",
    "        return [*p0, r]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def outerTrees(self, trees: list[list[int]]) -> list[list[int]]:\n",
    "        def cross(p: list[int], q: list[int], r: list[int]) -> int:\n",
    "            return (q[0] - p[0]) * (r[1] - q[1]) - (q[1] - p[1]) * (r[0] - q[0])\n",
    "\n",
    "        n = len(trees)\n",
    "        if n < 4:\n",
    "            return trees\n",
    "        leftMost = 0\n",
    "        for i, tree in enumerate(trees):\n",
    "            if tree[0] < trees[leftMost][0] or (\n",
    "                tree[0] == trees[leftMost][0] and tree[1] < trees[leftMost][1]\n",
    "            ):\n",
    "                leftMost = i\n",
    "        ans = []\n",
    "        vis = [False] * n\n",
    "        p = leftMost\n",
    "        while True:\n",
    "            q = (p + 1) % n\n",
    "            for r, tree in enumerate(trees):\n",
    "                if cross(trees[p], trees[q], tree) < 0:\n",
    "                    q = r\n",
    "            for i, b in enumerate(vis):\n",
    "                if (\n",
    "                    not b\n",
    "                    and i != p\n",
    "                    and i != q\n",
    "                    and cross(trees[p], trees[q], trees[i]) == 0\n",
    "                ):\n",
    "                    ans.append(trees[i])\n",
    "                    vis[i] = True\n",
    "            if not vis[q]:\n",
    "                ans.append(trees[q])\n",
    "                vis[q] = True\n",
    "            p = q\n",
    "            if p == leftMost:\n",
    "                break\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "\n",
    "    def outerTrees(self, trees: List[List[int]]) -> List[List[int]]:\n",
    "        def cross(p,q,r):\n",
    "            return(q[0] - p[0]) * (r[1] - q[1]) - (q[1] - p[1]) * (r[0] - q[0])\n",
    "\n",
    "        n = len(trees)\n",
    "        if n < 4:\n",
    "            return trees\n",
    "\n",
    "        trees.sort()\n",
    "\n",
    "        stack = [0]\n",
    "        used = [False] * n\n",
    "        #求凸包的下半部分\n",
    "        for i in range(1,n):\n",
    "            while len(stack) > 1 and cross(trees[stack[-2]],trees[stack[-1]],trees[i])<0:\n",
    "                used[stack.pop()] = False\n",
    "            used[i] = True\n",
    "            stack.append(i)\n",
    "        #凸包的上半部分\n",
    "        m = len(stack)\n",
    "        for i in range(n-2,-1,-1):\n",
    "            if not used[i]:\n",
    "                while len(stack) > m and cross(trees[stack[-2]],trees[stack[-1]],trees[i])<0:\n",
    "                    used[stack.pop()] = False\n",
    "                used[i] = True\n",
    "                stack.append(i)\n",
    "        stack.pop()\n",
    "        return [trees[i] for i in stack]\n",
    "            \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def outerTrees(self, trees: List[List[int]]) -> List[List[int]]:\n",
    "        def cross(p: List[int], q: List[int], r: List[int]) -> int:\n",
    "            return (q[0] - p[0]) * (r[1] - q[1]) - (q[1] - p[1]) * (r[0] - q[0])\n",
    "\n",
    "        n = len(trees)\n",
    "        if n < 4:\n",
    "            return trees\n",
    "\n",
    "        leftMost = 0\n",
    "        for i, tree in enumerate(trees):\n",
    "            if tree[0] < trees[leftMost][0] or (tree[0] == trees[leftMost][0] and tree[1] < trees[leftMost][1]):\n",
    "                leftMost = i\n",
    "\n",
    "        ans = []\n",
    "        vis = [False] * n\n",
    "        p = leftMost\n",
    "        while True:\n",
    "            q = (p + 1) % n\n",
    "            for r, tree in enumerate(trees):\n",
    "                # // 如果 r 在 pq 的右侧，则 q = r\n",
    "                if cross(trees[p], trees[q], tree) < 0:\n",
    "                    q = r\n",
    "            # 是否存在点 i, 使得 p q i 在同一条直线上\n",
    "            for i, b in enumerate(vis):\n",
    "                if not b and i != p and i != q and cross(trees[p], trees[q], trees[i]) == 0:\n",
    "                    ans.append(trees[i])\n",
    "                    vis[i] = True\n",
    "            if not vis[q]:\n",
    "                ans.append(trees[q])\n",
    "                vis[q] = True\n",
    "            p = q\n",
    "            if p == leftMost:\n",
    "                break\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def outerTrees(self, trees: List[List[int]]) -> List[List[int]]:\n",
    "        # 计算叉积\n",
    "        def cross(p,q,r):\n",
    "            return (q[0] - p[0]) * (r[1] - q[1]) - (q[1] - p[1]) * (r[0] - q[0])\n",
    "\n",
    "        n = len(trees)\n",
    "        if n < 4:\n",
    "            return trees\n",
    "\n",
    "        trees.sort()  # 根据x坐标对点进行排序\n",
    "\n",
    "        stack = [0]  # 存储凸包边界上的点的下标\n",
    "        used = [False] * n  # 记录点是否已经被使用\n",
    "        # 求凸包的下半部分\n",
    "        for i in range(1, n):\n",
    "            while len(stack) > 1 and cross(trees[stack[-2]], trees[stack[-1]], trees[i]) < 0:\n",
    "                used[stack.pop()] = False  # 栈顶的点不在凸包上，出栈并设置为未使用\n",
    "            used[i] = True  # 当前点在凸包上\n",
    "            stack.append(i)  # 将当前点加入栈中\n",
    "        # 凸包的上半部分\n",
    "        m = len(stack)  # 记录下半部分凸包的顶点数\n",
    "        for i in range(n-2, -1, -1):\n",
    "            if not used[i]:\n",
    "                while len(stack) > m and cross(trees[stack[-2]], trees[stack[-1]], trees[i]) < 0:\n",
    "                    used[stack.pop()] = False\n",
    "                used[i] = True\n",
    "                stack.append(i)\n",
    "        stack.pop()  # 最后栈顶与栈底重复，需要出栈\n",
    "        return [trees[i] for i in stack]  # 根据下标获取对应点的坐标，返回凸包上的点的坐标列表"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def cross(point1, point2, point3):\n",
    "    x1y2 = (point2[0] - point1[0]) * (point3[1] - point2[1])\n",
    "    x2y1 = (point3[0] - point2[0]) * (point2[1] - point1[1])\n",
    "    return x1y2 - x2y1\n",
    "\n",
    "def convex(data):\n",
    "    hull = []\n",
    "    data.sort()\n",
    "    for i in range(len(data)):\n",
    "        while len(hull) > 1 and cross(data[hull[-2]], data[hull[-1]], data[i]) < 0:\n",
    "            hull.pop()\n",
    "        hull.append(i)\n",
    "    for i in reversed(range(len(data))):\n",
    "        while len(hull) > 1 and cross(data[hull[-2]], data[hull[-1]], data[i]) < 0:\n",
    "            hull.pop()\n",
    "        hull.append(i)\n",
    "    return [data[i] for i in set(hull)]\n",
    "\n",
    "class Solution:\n",
    "    def outerTrees(self, trees):\n",
    "        return convex(trees)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def outerTrees(self, trees: List[List[int]]) -> List[List[int]]:\n",
    "        def cross(p: List[int], q: List[int], r: List[int]) -> int:\n",
    "            return (q[0] - p[0]) * (r[1] - q[1]) - (q[1] - p[1]) * (r[0] - q[0])\n",
    "\n",
    "        n = len(trees)\n",
    "        if n < 4:\n",
    "            return trees\n",
    "\n",
    "        leftMost = 0\n",
    "        for i, tree in enumerate(trees):\n",
    "            if tree[0] < trees[leftMost][0] or (tree[0] == trees[leftMost][0] and tree[1] < trees[leftMost][1]):\n",
    "                leftMost = i\n",
    "\n",
    "        ans = []\n",
    "        vis = [False] * n\n",
    "        p = leftMost\n",
    "        while True:\n",
    "            q = (p + 1) % n\n",
    "            for r, tree in enumerate(trees):\n",
    "                # // 如果 r 在 pq 的右侧，则 q = r\n",
    "                if cross(trees[p], trees[q], tree) < 0:\n",
    "                    q = r\n",
    "            # 是否存在点 i, 使得 p q i 在同一条直线上\n",
    "            for i, b in enumerate(vis):\n",
    "                if not b and i != p and i != q and cross(trees[p], trees[q], trees[i]) == 0:\n",
    "                    ans.append(trees[i])\n",
    "                    vis[i] = True\n",
    "            if not vis[q]:\n",
    "                ans.append(trees[q])\n",
    "                vis[q] = True\n",
    "            p = q\n",
    "            if p == leftMost:\n",
    "                break\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def outerTrees(self, trees: list[list[int]]) -> list[list[int]]:\n",
    "        def cross(p: list[int], q: list[int], r: list[int]) -> int:\n",
    "            return (q[0] - p[0]) * (r[1] - q[1]) - (q[1] - p[1]) * (r[0] - q[0])\n",
    "\n",
    "        n = len(trees)\n",
    "        if n < 4:\n",
    "            return trees\n",
    "        trees.sort()\n",
    "        hull = [0]\n",
    "        used = [False] * n\n",
    "        for i in range(1, n):\n",
    "            while (\n",
    "                len(hull) > 1 and cross(trees[hull[-2]], trees[hull[-1]], trees[i]) < 0\n",
    "            ):\n",
    "                used[hull.pop()] = False\n",
    "            used[i] = True\n",
    "            hull.append(i)\n",
    "        m = len(hull)\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            if not used[i]:\n",
    "                while (\n",
    "                    len(hull) > m\n",
    "                    and cross(trees[hull[-2]], trees[hull[-1]], trees[i]) < 0\n",
    "                ):\n",
    "                    used[hull.pop()] = False\n",
    "                used[i] = True\n",
    "                hull.append(i)\n",
    "        hull.pop()\n",
    "        return [trees[i] for i in hull]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def outerTrees(self, trees: List[List[int]]) -> List[List[int]]:\n",
    "        n = len(trees)\n",
    "        if n < 4: \n",
    "            return trees\n",
    "        \n",
    "        def cross(p, q, r):\n",
    "            return (q[0] - p[0]) * (r[1] - q[1]) - (q[1] - p[1]) * (r[0] - q[0])\n",
    "\n",
    "        trees.sort()\n",
    "\n",
    "        hull = [0]\n",
    "        used = [False] * n\n",
    "        for i in range(1, n):\n",
    "            while len(hull) > 1 and cross(trees[hull[-2]], trees[hull[-1]], trees[i]) < 0:\n",
    "               used[hull.pop()] = False\n",
    "            used[i] = True\n",
    "            hull.append(i)\n",
    "        \n",
    "        m = len(hull)\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            if not used[i]:\n",
    "                while len(hull) > m and cross(trees[hull[-2]], trees[hull[-1]], trees[i]) < 0:\n",
    "                    used[hull.pop()] = True\n",
    "                used[i] = True\n",
    "                hull.append(i)\n",
    "        hull.pop()\n",
    "        return [trees[i] for i in hull]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def outerTrees(self, trees: List[List[int]]) -> List[List[int]]:\n",
    "        def cross(p: List[int], q: List[int], r: List[int]) -> int:\n",
    "            return (q[0] - p[0]) * (r[1] - q[1]) - (q[1] - p[1]) * (r[0] - q[0])\n",
    "\n",
    "        n = len(trees)\n",
    "        # if n < 4:\n",
    "        #     return trees\n",
    "\n",
    "        leftMost = 0\n",
    "        for i, tree in enumerate(trees):\n",
    "            if tree[0] < trees[leftMost][0] or (tree[0] == trees[leftMost][0] and tree[1] < trees[leftMost][1]):\n",
    "                leftMost = i\n",
    "\n",
    "        ans = []\n",
    "        vis = [False] * n\n",
    "        p = leftMost\n",
    "        while True:\n",
    "            q = (p + 1) % n\n",
    "            for r, tree in enumerate(trees):\n",
    "                # // 如果 r 在 pq 的右侧，则 q = r\n",
    "                if cross(trees[p], trees[q], tree) < 0:\n",
    "                    q = r\n",
    "            # 是否存在点 i, 使得 p q i 在同一条直线上\n",
    "            for i, b in enumerate(vis):\n",
    "                if not b and i != p and i != q and cross(trees[p], trees[q], trees[i]) == 0:\n",
    "                    ans.append(trees[i])\n",
    "                    vis[i] = True\n",
    "            if not vis[q]:\n",
    "                ans.append(trees[q])\n",
    "                vis[q] = True\n",
    "            p = q\n",
    "            if p == leftMost:\n",
    "                break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def outerTrees(self, trees: List[List[int]]) -> List[List[int]]:\n",
    "        def cross(p: List[int], q: List[int], r: List[int]) -> int:\n",
    "            return (q[0] - p[0]) * (r[1] - q[1]) - (q[1] - p[1]) * (r[0] - q[0])\n",
    "\n",
    "        hull = []\n",
    "        trees.sort()\n",
    "        for i in range(len(trees)):\n",
    "            while len(hull) > 1 and cross(trees[hull[-2]], trees[hull[-1]], trees[i]) < 0:\n",
    "                hull.pop()\n",
    "            hull.append(i)\n",
    "        for i in reversed(range(len(trees))):\n",
    "            while len(hull) > 1 and cross(trees[hull[-2]], trees[hull[-1]], trees[i]) < 0:\n",
    "                hull.pop()\n",
    "            hull.append(i)\n",
    "\n",
    "        return [trees[i] for i in set(hull)]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def outerTrees(self, trees: List[List[int]]) -> List[List[int]]:\n",
    "        # 求扫过的面积 如果<0 说明需要更新\n",
    "        def cross(p: List[int], q: List[int], r: List[int]) -> int:\n",
    "            return (q[0] - p[0]) * (r[1] - q[1]) - (q[1] - p[1]) * (r[0] - q[0])\n",
    "        \n",
    "        n = len(trees)\n",
    "        if n < 4:\n",
    "            return trees\n",
    "\n",
    "        \n",
    "        trees.sort()\n",
    "\n",
    "        hull = [0]\n",
    "        used = [False] * n\n",
    "        # 求凸包下半部分\n",
    "        for i in range(1, n):\n",
    "            while len(hull) > 1 and cross(trees[hull[-2]], trees[hull[-1]], trees[i]) < 0:\n",
    "                used[hull.pop()] = False\n",
    "            used[i] = True\n",
    "            hull.append(i)\n",
    "        # 求凸包的上半部分\n",
    "        m = len(hull)\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            if not used[i]:\n",
    "                while len(hull) > m and cross(trees[hull[-2]], trees[hull[-1]], trees[i]) < 0:\n",
    "                    used[hull.pop()] = False\n",
    "                used[i] = True\n",
    "                hull.append(i)\n",
    "        # hull[0] 是起点 同时参加上半部分的检测 所以要删掉\n",
    "        hull.pop()\n",
    "        return [trees[i] for i in hull]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def cross(vector1, vector2):\n",
    "    return vector1[0] * vector2[1] - vector2[0] * vector1[1]\n",
    "\n",
    "def check(point1, point2, point3):\n",
    "    vector1 = (point2[0] - point1[0]), (point2[1] - point1[1])\n",
    "    vector2 = (point3[0] - point2[0]), (point3[1] - point2[1])\n",
    "    return cross(vector1, vector2)\n",
    "\n",
    "def convex(data):\n",
    "    hull = []\n",
    "    data.sort()\n",
    "    for i in range(len(data)):\n",
    "        while len(hull) > 1 and check(data[hull[-2]], data[hull[-1]], data[i]) < 0:\n",
    "            hull.pop()\n",
    "        hull.append(i)\n",
    "    for i in reversed(range(len(data))):\n",
    "        while len(hull) > 1 and check(data[hull[-2]], data[hull[-1]], data[i]) < 0:\n",
    "            hull.pop()\n",
    "        hull.append(i)\n",
    "    return [data[i] for i in set(hull)]\n",
    "\n",
    "class Solution:\n",
    "    def outerTrees(self, trees):\n",
    "        return convex(trees)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def outerTrees(self, trees: List[List[int]]) -> List[List[int]]:\n",
    "        trees.sort()\n",
    "        n = len(trees)\n",
    "\n",
    "        if n < 4:\n",
    "            return trees\n",
    "\n",
    "        def cross(x, y, z):\n",
    "            return (y[0] - x[0]) * (z[1] - x[1]) - (y[1] - x[1]) * (z[0] - x[0])\n",
    "        \n",
    "        used = [False] * n\n",
    "        stk = [0]\n",
    "\n",
    "        n = len(trees)\n",
    "        for i in range(1, n):\n",
    "            while len(stk) > 1 and cross(trees[stk[-2]], trees[stk[-1]], trees[i]) < 0:\n",
    "                used[stk.pop()] = False\n",
    "            used[i] = True\n",
    "            stk.append(i)\n",
    "        m = len(stk)\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            if used[i]:\n",
    "                continue\n",
    "            while len(stk) > m and cross(trees[stk[-2]], trees[stk[-1]], trees[i]) < 0:\n",
    "                used[stk.pop()] = False\n",
    "            used[i] = True\n",
    "            stk.append(i)\n",
    "        stk.pop()\n",
    "        return [trees[i] for i in stk]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def outerTrees(self, trees: List[List[int]]) -> List[List[int]]:\n",
    "        def cross(p, q, r):\n",
    "            return (q[0] - p[0]) * (r[1] - q[1]) - (q[1] - p[1]) * (r[0] - q[0])\n",
    "\n",
    "        n = len(trees)\n",
    "        if n < 4:\n",
    "            return trees\n",
    "\n",
    "        leftMost = 0\n",
    "        for i, tree in enumerate(trees):\n",
    "            if tree[0] < trees[leftMost][0] or (tree[0] == trees[leftMost][0] and tree[1] < trees[leftMost][1]):\n",
    "                leftMost = i\n",
    "\n",
    "        ans = []\n",
    "        vis = [False] * n\n",
    "        p = leftMost\n",
    "        while True:\n",
    "            q = (p + 1) % n\n",
    "            for r, tree in enumerate(trees):\n",
    "                # // 如果 r 在 pq 的右侧，则 q = r\n",
    "                if cross(trees[p], trees[q], tree) < 0:\n",
    "                    q = r\n",
    "            # 是否存在点 i, 使得 p q i 在同一条直线上\n",
    "            for i, b in enumerate(vis):\n",
    "                if not b and i != p and i != q and cross(trees[p], trees[q], trees[i]) == 0:\n",
    "                    ans.append(trees[i])\n",
    "                    vis[i] = True\n",
    "            if not vis[q]:\n",
    "                ans.append(trees[q])\n",
    "                vis[q] = True\n",
    "            p = q\n",
    "            if p == leftMost:\n",
    "                break\n",
    "        return sorted(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def outerTrees(self, trees: List[List[int]]) -> List[List[int]]:\n",
    "        trees.sort()\n",
    "        stk = []\n",
    "        for t in trees:\n",
    "            i = len(stk) - 1\n",
    "            while i > 0 and (t[0] - stk[i][0]) * (stk[i][1] - stk[i-1][1]) > (stk[i][0] - stk[i-1][0]) * (t[1] - stk[i][1]):\n",
    "                stk.pop()\n",
    "                i -= 1 \n",
    "            stk.append(t)\n",
    "        N = len(stk)\n",
    "        for j in range(len(trees)-1,-1,-1):\n",
    "            t = trees[j]\n",
    "            i = len(stk) - 1\n",
    "            while i > N and (t[0] - stk[i][0]) * (stk[i][1] - stk[i-1][1]) > (stk[i][0] - stk[i-1][0]) * (t[1] - stk[i][1]):\n",
    "                stk.pop()\n",
    "                i -= 1 \n",
    "            stk.append(t)\n",
    "        stk.sort()\n",
    "        ans = [stk[0]]\n",
    "        for i in range(1, len(stk)):\n",
    "            if stk[i] != stk[i-1]:\n",
    "                ans.append(stk[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def outerTrees(self, trees: List[List[int]]) -> List[List[int]]:\n",
    "        trees.sort()\n",
    "        hall = []\n",
    "        used = set()\n",
    "        for tree in trees:\n",
    "            while len(hall) >= 2 and self.area(hall[-2], hall[-1], tree) > 0:\n",
    "                used.remove(tuple(hall[-1]))\n",
    "                hall.pop()\n",
    "            hall.append(tree)\n",
    "            used.add(tuple(tree))\n",
    "        used.remove(tuple(hall[0]))\n",
    "        for tree in reversed(trees):\n",
    "            if tuple(tree) in used:\n",
    "                continue\n",
    "            while len(hall) >= 2 and self.area(hall[-2], hall[-1], tree) > 0:\n",
    "                used.remove(tuple(hall[-1]))\n",
    "                hall.pop()\n",
    "            hall.append(tree)\n",
    "            used.add(tuple(tree))\n",
    "        return hall[:-1]\n",
    "    \n",
    "    # 计算cross积（向量形成平行四边形面积，夹角为顺时针为负，逆时针为正）\n",
    "    def area(self, a, b, c):\n",
    "        return self.cross([b[0] - a[0], b[1] - a[1]], [c[0] - a[0], c[1] - a[1]])\n",
    "    \n",
    "    def cross(self, x, y):\n",
    "        return x[0] * y[1] - x[1] * y[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def outerTrees(self, trees: List[List[int]]) -> List[List[int]]:\n",
    "        def cross(p: List[int], q: List[int], r: List[int]) -> int:\n",
    "            return (q[0] - p[0]) * (r[1] - q[1]) - (q[1] - p[1]) * (r[0] - q[0])\n",
    "\n",
    "        n = len(trees)\n",
    "        if n < 4:\n",
    "            return trees\n",
    "\n",
    "        leftMost = 0\n",
    "        for i, tree in enumerate(trees):\n",
    "            if tree[0] < trees[leftMost][0] or (tree[0] == trees[leftMost][0] and tree[1] < trees[leftMost][1]):\n",
    "                leftMost = i\n",
    "\n",
    "        ans = []\n",
    "        vis = [False] * n\n",
    "        p = leftMost\n",
    "        while True:\n",
    "            q = (p + 1) % n\n",
    "            for r, tree in enumerate(trees):\n",
    "                # // 如果 r 在 pq 的右侧，则 q = r\n",
    "                if cross(trees[p], trees[q], tree) < 0:\n",
    "                    q = r\n",
    "            # 是否存在点 i, 使得 p q i 在同一条直线上\n",
    "            for i, b in enumerate(vis):\n",
    "                if not b and i != p and i != q and cross(trees[p], trees[q], trees[i]) == 0:\n",
    "                    ans.append(trees[i])\n",
    "                    vis[i] = True\n",
    "            if not vis[q]:\n",
    "                ans.append(trees[q])\n",
    "                vis[q] = True\n",
    "            p = q\n",
    "            if p == leftMost:\n",
    "                break\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def outerTrees(self, trees: List[List[int]]) -> List[List[int]]:\n",
    "        n = len(trees)\n",
    "        trees.sort()\n",
    "\n",
    "        # s1 top of stack, p waitting for put\n",
    "        def cross(s2, s1, p):\n",
    "            return (s1[0]-s2[0])*(p[1]-s1[1]) - (s1[1]-s2[1])*(p[0]-s1[0])\n",
    "        \n",
    "        ans_down = []\n",
    "        for i in range(n):\n",
    "            while len(ans_down) > 1 and cross(ans_down[-2], ans_down[-1], trees[i]) < 0:\n",
    "                ans_down.pop(-1)\n",
    "            ans_down.append(trees[i])\n",
    "\n",
    "        ans_up = []\n",
    "        for i in range(n-1, -1, -1):\n",
    "            while len(ans_up) > 1 and cross(ans_up[-2], ans_up[-1], trees[i]) < 0:\n",
    "                ans_up.pop(-1)\n",
    "            ans_up.append(trees[i])\n",
    "\n",
    "        for point in ans_up:\n",
    "            if point not in ans_down:\n",
    "                ans_down.append(point)\n",
    "\n",
    "        return ans_down        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def outerTrees(self, trees: List[List[int]]) -> List[List[int]]:\n",
    "        cross = lambda o, b, a: (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])\n",
    "        lower = []\n",
    "        upper = []\n",
    "        trees.sort()\n",
    "        for t in trees:\n",
    "            while len(lower) > 1 and cross(lower[-2], lower[-1], t) > 0:\n",
    "                lower.pop()\n",
    "            lower.append(tuple(t))\n",
    "        trees.sort(reverse = True)\n",
    "        for t in trees:\n",
    "            while len(upper) > 1 and cross(upper[-2], upper[-1], t) > 0:\n",
    "                upper.pop()\n",
    "            upper.append(tuple(t))\n",
    "        return sorted(set(upper + lower))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def outerTrees(self, trees: List[List[int]]) -> List[List[int]]:\r\n",
    "        def cross(p,q,r):\r\n",
    "            return (q[0]-p[0])*(r[1]-q[1])-(q[1]-p[1])*(r[0]-q[0])\r\n",
    "        if len(trees)<4:\r\n",
    "            return trees\r\n",
    "        \r\n",
    "        trees.sort()\r\n",
    "        hull=[0]\r\n",
    "        used=[False]*len(trees)\r\n",
    "        for i in range(1,len(trees)):            \r\n",
    "            while len(hull)>1 and cross(trees[hull[-2]],trees[hull[-1]],trees[i])<0:\r\n",
    "                used[hull.pop()]=False\r\n",
    "            hull.append(i)\r\n",
    "            used[i]=True\r\n",
    "        \r\n",
    "        m=len(hull)\r\n",
    "        for i in range(len(trees)-2,-1,-1):\r\n",
    "            if used[i]:\r\n",
    "                continue\r\n",
    "            while len(hull)>m and cross(trees[hull[-2]],trees[hull[-1]],trees[i])<0:\r\n",
    "                used[hull.pop()]=False\r\n",
    "            hull.append(i)\r\n",
    "            used[i]=True\r\n",
    "        hull.pop()\r\n",
    "        return [trees[i] for i in hull]       \r\n",
    "        \r\n",
    "\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def outerTrees(self, points: List[List[int]]) -> List[List[int]]:\n",
    "        def oriented(p, q, r):\n",
    "            return (q[0] - p[0]) * (r[1] - p[1]) - (q[1] - p[1]) * (\n",
    "                    r[0] - p[0])  # 叉积方向为正数，逆时针\n",
    "        if len(points) < 4:\n",
    "            return points\n",
    "        points.sort()\n",
    "        hull = [points[0], points[1]]\n",
    "        m = set()\n",
    "        for i in range(2, len(points)):\n",
    "            r = points[i]\n",
    "            while len(hull) > 1 and oriented(hull[-2], hull[-1], r) < 0:\n",
    "                hull.pop()\n",
    "            hull.append(r)\n",
    "        for point in hull:\n",
    "            m.add(tuple(point))\n",
    "        points = points[::-1]\n",
    "        for r in points[1:]:\n",
    "            while len(hull)>1 and oriented(hull[-2], hull[-1], r) < 0:\n",
    "                hull.pop()\n",
    "            if tuple(r) not in m:\n",
    "                hull.append(r)\n",
    "        return hull\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def outerTrees(self, trees: List[List[int]]) -> List[List[int]]:\n",
    "        # 计算叉积\n",
    "        def cross(p,q,r):\n",
    "            return (q[0] - p[0]) * (r[1] - q[1]) - (q[1] - p[1]) * (r[0] - q[0])\n",
    "\n",
    "        n = len(trees)\n",
    "        if n < 4:\n",
    "            return trees\n",
    "\n",
    "        trees.sort()  # 根据x坐标对点进行排序\n",
    "\n",
    "        stack = [0]  # 存储凸包边界上的点的下标\n",
    "        used = [False] * n  # 记录点是否已经被使用\n",
    "        # 求凸包的下半部分\n",
    "        for i in range(1, n):\n",
    "            while len(stack) > 1 and cross(trees[stack[-2]], trees[stack[-1]], trees[i]) < 0:\n",
    "                used[stack.pop()] = False  # 栈顶的点不在凸包上，出栈并设置为未使用\n",
    "            used[i] = True  # 当前点在凸包上\n",
    "            stack.append(i)  # 将当前点加入栈中\n",
    "        # 凸包的上半部分\n",
    "        m = len(stack)  # 记录下半部分凸包的顶点数\n",
    "        for i in range(n-2, -1, -1):\n",
    "            if not used[i]:\n",
    "                while len(stack) > m and cross(trees[stack[-2]], trees[stack[-1]], trees[i]) < 0:\n",
    "                    used[stack.pop()] = False\n",
    "                used[i] = True\n",
    "                stack.append(i)\n",
    "        stack.pop()  # 最后栈顶与栈底重复，需要出栈\n",
    "        return [trees[i] for i in stack]  # 根据下标获取对应点的坐标，返回凸包上的点的坐标列表"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def outerTrees(self, trees: List[List[int]]) -> List[List[int]]:\n",
    "        def cross(p: List[int], q: List[int], r: List[int]) -> int:\n",
    "            return (q[0] - p[0]) * (r[1] - q[1]) - (q[1] - p[1]) * (r[0] - q[0])\n",
    "\n",
    "        n = len(trees)\n",
    "        if n < 4:\n",
    "            return trees\n",
    "\n",
    "        leftMost = 0\n",
    "        for i, tree in enumerate(trees):\n",
    "            if tree[0] < trees[leftMost][0] or (tree[0] == trees[leftMost][0] and tree[1] < trees[leftMost][1]):\n",
    "                leftMost = i\n",
    "\n",
    "        ans = []\n",
    "        vis = [False] * n\n",
    "        p = leftMost\n",
    "        while True:\n",
    "            q = (p + 1) % n\n",
    "            for r, tree in enumerate(trees):\n",
    "                # // 如果 r 在 pq 的右侧，则 q = r\n",
    "                if cross(trees[p], trees[q], tree) < 0:\n",
    "                    q = r\n",
    "            # 是否存在点 i, 使得 p q i 在同一条直线上\n",
    "            for i, b in enumerate(vis):\n",
    "                if not b and i != p and i != q and cross(trees[p], trees[q], trees[i]) == 0:\n",
    "                    ans.append(trees[i])\n",
    "                    vis[i] = True\n",
    "            if not vis[q]:\n",
    "                ans.append(trees[q])\n",
    "                vis[q] = True\n",
    "            p = q\n",
    "            if p == leftMost:\n",
    "                break\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def outerTrees(self, trees: List[List[int]]) -> List[List[int]]:\n",
    "        def orientation(p, q, r):\n",
    "            return (q[0] - p[0]) * (r[1] - q[1]) - (q[1] - p[1]) * (r[0] - q[0])\n",
    "\n",
    "        n = len(trees)\n",
    "        if n < 4:\n",
    "            return trees\n",
    "\n",
    "        leftMost = 0\n",
    "        for i, tree in enumerate(trees):\n",
    "            if tree[0] < trees[leftMost][0] or (tree[0] == trees[leftMost][0] and tree[1] < trees[leftMost][1]):\n",
    "                leftMost = i\n",
    "\n",
    "        ans = []\n",
    "        vis = [False] * n\n",
    "        p = leftMost\n",
    "        while True:\n",
    "            q = (p + 1) % n\n",
    "            for r, tree in enumerate(trees):\n",
    "                # // 如果 r 在 pq 的右侧，则 q = r\n",
    "                if orientation(trees[p], trees[q], tree) < 0:\n",
    "                    q = r\n",
    "            # 是否存在点 i, 使得 p q i 在同一条直线上\n",
    "            for i, b in enumerate(vis):\n",
    "                if not b and i != p and i != q and orientation(trees[p], trees[q], trees[i]) == 0:\n",
    "                    ans.append(trees[i])\n",
    "                    vis[i] = True\n",
    "            if not vis[q]:\n",
    "                ans.append(trees[q])\n",
    "                vis[q] = True\n",
    "            p = q\n",
    "            if p == leftMost:\n",
    "                break\n",
    "        return sorted(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def outerTrees(self, trees: list[list[int]]) -> list[list[int]]:\n",
    "        def cross(p: list[int], q: list[int], r: list[int]) -> int:\n",
    "            return (q[0] - p[0]) * (r[1] - q[1]) - (q[1] - p[1]) * (r[0] - q[0])\n",
    "\n",
    "        def distance(p: list[int], q: list[int]) -> int:\n",
    "            return (p[0] - q[0]) * (p[0] - q[0]) + (p[1] - q[1]) * (p[1] - q[1])\n",
    "\n",
    "        n = len(trees)\n",
    "        if n < 4:\n",
    "            return trees\n",
    "        bottom = 0\n",
    "        for i, tree in enumerate(trees):\n",
    "            if tree[1] < trees[bottom][1]:\n",
    "                bottom = i\n",
    "        trees[bottom], trees[0] = trees[0], trees[bottom]\n",
    "\n",
    "        def cmp(a: list[int], b: list[int]) -> int:\n",
    "            diff = -cross(trees[0], a, b)\n",
    "            return diff if diff else distance(trees[0], a) - distance(trees[0], b)\n",
    "\n",
    "        trees[1:] = sorted(trees[1:], key=cmp_to_key(cmp))\n",
    "        r = n - 1\n",
    "        while r >= 0 and cross(trees[0], trees[n - 1], trees[r]) == 0:\n",
    "            r -= 1\n",
    "        l, h = r + 1, n - 1\n",
    "        while l < h:\n",
    "            trees[l], trees[h] = trees[h], trees[l]\n",
    "            l += 1\n",
    "            h = -1\n",
    "        stack = [0, 1]\n",
    "        for i in range(2, n):\n",
    "            while (\n",
    "                len(stack) > 1\n",
    "                and cross(trees[stack[-2]], trees[stack[-1]], trees[i]) < 0\n",
    "            ):\n",
    "                stack.pop()\n",
    "            stack.append(i)\n",
    "        return [trees[i] for i in stack]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def outerTrees(self, trees: List[List[int]]) -> List[List[int]]:\n",
    "        n = len(trees)\n",
    "        if n < 4: \n",
    "            return trees\n",
    "        \n",
    "        def cross(p, q, r):\n",
    "            return (q[0] - p[0]) * (r[1] - q[1]) - (q[1] - p[1]) * (r[0] - q[0])\n",
    "\n",
    "        trees.sort()\n",
    "\n",
    "        hull = [0]\n",
    "        used = [False] * n\n",
    "        for i in range(1, n):\n",
    "            while len(hull) > 1 and cross(trees[hull[-2]], trees[hull[-1]], trees[i]) < 0:\n",
    "               used[hull.pop()] = False\n",
    "            used[i] = True\n",
    "            hull.append(i)\n",
    "        \n",
    "        m = len(hull)\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            if not used[i]:\n",
    "                while len(hull) > m and cross(trees[hull[-2]], trees[hull[-1]], trees[i]) < 0:\n",
    "                    used[hull.pop()] = True\n",
    "                used[i] = True\n",
    "                hull.append(i)\n",
    "        hull.pop()\n",
    "        return [trees[i] for i in hull]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def cross(vector1, vector2):\n",
    "    return vector1[0] * vector2[1] - vector2[0] * vector1[1]\n",
    "\n",
    "def check(point1, point2, point3):\n",
    "    vector1 = (point2[0] - point1[0]), (point2[1] - point1[1])\n",
    "    vector2 = (point3[0] - point2[0]), (point3[1] - point2[1])\n",
    "    return cross(vector1, vector2)\n",
    "\n",
    "def convex(points):\n",
    "    hull = []\n",
    "    idx = sorted(range(len(points)), key=lambda x:points[x])\n",
    "    for i in idx:\n",
    "        while len(hull) > 1 and check(points[hull[-2]], points[hull[-1]], points[i]) < 0: hull.pop()\n",
    "        if i not in hull: hull.append(i)\n",
    "    for i in reversed(idx):\n",
    "        while len(hull) > 1 and check(points[hull[-2]], points[hull[-1]], points[i]) < 0: hull.pop()\n",
    "        if i not in hull: hull.append(i)\n",
    "    return hull\n",
    "\n",
    "class Solution:\n",
    "    def outerTrees(self, trees):\n",
    "        return [trees[i] for i in convex(trees)]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def outerTrees(self, trees: List[List[int]]) -> List[List[int]]:\n",
    "        def cross(p, q, r) -> int:\n",
    "            return (q[0] - p[0]) * (r[1] - q[1]) - (q[1] - p[1]) * (r[0] - q[0])\n",
    "        \n",
    "        n = len(trees)\n",
    "        if n < 4:\n",
    "            return trees\n",
    "\n",
    "        leftMost = 0\n",
    "        for i, tree in enumerate(trees):\n",
    "            if tree[0] < trees[leftMost][0] or (tree[0] == trees[leftMost][0] and tree[1] < trees[leftMost][1]):\n",
    "                leftMost = i\n",
    "\n",
    "        ans = []        \n",
    "        vis = [False] * n\n",
    "        p = leftMost\n",
    "\n",
    "        while True:\n",
    "            q = (p + 1) % n\n",
    "            for r, tree in enumerate(trees):\n",
    "                if cross(trees[p], trees[q], tree) < 0:\n",
    "                    q = r\n",
    "            for i, b in enumerate(vis):\n",
    "                if not b and i != p and i != q and cross(trees[p], trees[q], trees[i]) == 0:\n",
    "                    ans.append(trees[i])\n",
    "                    vis[i] = True\n",
    "            if not vis[q]:\n",
    "                ans.append(trees[q])\n",
    "                vis[q] = True\n",
    "            p = q\n",
    "            if p == leftMost:\n",
    "                break\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def outerTrees(self, trees: List[List[int]]) -> List[List[int]]:\n",
    "        if len(trees) <= 1:\n",
    "            return trees\n",
    "        def cross(p, q, r):\n",
    "            res = (q[0] - p[0]) * (r[1] - q[1]) - (q[1] - p[1]) * (r[0] - q[0])\n",
    "            return res\n",
    "\n",
    "        def cal(trees):\n",
    "            n = len(trees)\n",
    "            stack, top = list([0 for _ in range(n)]), 1\n",
    "            stack[1] = 1\n",
    "            for i in range(2, n):\n",
    "                while stack and top > 0 and cross(trees[stack[top-1]], trees[stack[top]], trees[i]) < 0:\n",
    "                    top -= 1\n",
    "                top += 1\n",
    "                stack[top] = i\n",
    "            return stack[: top+1]\n",
    "        trees.sort()\n",
    "        x1 = cal(trees)\n",
    "        x2 = cal([[i, -j] for i, j in trees])\n",
    "        return [trees[i] for i in set(x1+ x2)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def outerTrees(self, trees: List[List[int]]) -> List[List[int]]:\n",
    "        def cross(p: List[int], q: List[int], r: List[int]) -> int:\n",
    "            return (q[0] - p[0]) * (r[1] - q[1]) - (q[1] - p[1]) * (r[0] - q[0])\n",
    "\n",
    "        n = len(trees)\n",
    "        if n < 4:\n",
    "            return trees\n",
    "\n",
    "        leftMost = 0\n",
    "        for i, tree in enumerate(trees):\n",
    "            if tree[0] < trees[leftMost][0] or (tree[0] == trees[leftMost][0] and tree[1] < trees[leftMost][1]):\n",
    "                leftMost = i\n",
    "\n",
    "        ans = []\n",
    "        vis = [False] * n\n",
    "        p = leftMost\n",
    "        while True:\n",
    "            q = (p + 1) % n\n",
    "            for r, tree in enumerate(trees):\n",
    "                # // 如果 r 在 pq 的右侧，则 q = r\n",
    "                if cross(trees[p], trees[q], tree) < 0:\n",
    "                    q = r\n",
    "            # 是否存在点 i, 使得 p q i 在同一条直线上\n",
    "            for i, b in enumerate(vis):\n",
    "                if not b and i != p and i != q and cross(trees[p], trees[q], trees[i]) == 0:\n",
    "                    ans.append(trees[i])\n",
    "                    vis[i] = True\n",
    "            if not vis[q]:\n",
    "                ans.append(trees[q])\n",
    "                vis[q] = True\n",
    "            p = q\n",
    "            if p == leftMost:\n",
    "                break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def outerTrees(self, trees: List[List[int]]) -> List[List[int]]:\n",
    "        # 斜率公式换算为乘积\n",
    "        def sign(p, q, r):\n",
    "            return (p[0] - r[0])*(q[1] - r[1]) - (p[1] - r[1])*(q[0] - r[0])\n",
    "        \n",
    "        # 判断添加点 r 是否在前面两点连线的右边\n",
    "        def check_valid(points, r):\n",
    "            points.append(r)\n",
    "            while len(points) >= 3 and sign(*points[-3:]) < 0:\n",
    "                points.pop(-2)\n",
    "            return points\n",
    "        \n",
    "        trees.sort(key = lambda p: (p[0], p[1]))\n",
    "        lower = reduce(check_valid, trees, [])\n",
    "        upper = reduce(check_valid, trees[::-1], [])\n",
    "        return lower + list(filter(lambda p: p not in lower, upper))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def outerTrees(self, trees: List[List[int]]) -> List[List[int]]:\n",
    "        def cross(p: List[int], q: List[int], r: List[int]) -> int:\n",
    "            return (q[0] - p[0]) * (r[1] - q[1]) - (q[1] - p[1]) * (r[0] - q[0])\n",
    "\n",
    "        n = len(trees)\n",
    "        if n < 4:\n",
    "            return trees\n",
    "\n",
    "        leftMost = 0\n",
    "        for i, tree in enumerate(trees):\n",
    "            if tree[0] < trees[leftMost][0] or (tree[0] == trees[leftMost][0] and tree[1] < trees[leftMost][1]):\n",
    "                leftMost = i\n",
    "\n",
    "        ans = []\n",
    "        vis = [False] * n\n",
    "        p = leftMost\n",
    "        while True:\n",
    "            q = (p + 1) % n\n",
    "            for r, tree in enumerate(trees):\n",
    "                # // 如果 r 在 pq 的右侧，则 q = r\n",
    "                if cross(trees[p], trees[q], tree) < 0:\n",
    "                    q = r\n",
    "            # 是否存在点 i, 使得 p q i 在同一条直线上\n",
    "            for i, b in enumerate(vis):\n",
    "                if not b and i != p and i != q and cross(trees[p], trees[q], trees[i]) == 0:\n",
    "                    ans.append(trees[i])\n",
    "                    vis[i] = True\n",
    "            if not vis[q]:\n",
    "                ans.append(trees[q])\n",
    "                vis[q] = True\n",
    "            p = q\n",
    "            if p == leftMost:\n",
    "                break\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def outerTrees(self, trees: List[List[int]]) -> List[List[int]]:\n",
    "        def cross(p: List[int], q: List[int], r: List[int]) -> int:\n",
    "            return (q[0] - p[0]) * (r[1] - q[1]) - (q[1] - p[1]) * (r[0] - q[0])\n",
    "        \n",
    "        n = len(trees)\n",
    "        if n < 4:\n",
    "            return trees\n",
    "        \n",
    "        leftMost = 0\n",
    "        for i, tree in enumerate(trees):\n",
    "            if tree[0] < trees[leftMost][0] or (tree[0] == trees[leftMost][0] and tree[1] < trees[leftMost][1]):\n",
    "                leftMost = i\n",
    "\n",
    "        ans = []\n",
    "        vis = [False] * n\n",
    "        p = leftMost\n",
    "        while True:\n",
    "            q = (p + 1) % n\n",
    "            for r, tree in enumerate(trees):\n",
    "                if cross(trees[p], trees[q], tree) < 0:\n",
    "                    q = r\n",
    "            \n",
    "            for i, b in enumerate(vis):\n",
    "                if not b and i != p and i != q and cross(trees[p], trees[q], trees[i]) == 0:\n",
    "                    ans.append(trees[i])\n",
    "                    vis[i] = True\n",
    "            if not vis[q]:\n",
    "                ans.append(trees[q])\n",
    "                vis[q] = True\n",
    "            p = q\n",
    "            if p == leftMost:\n",
    "                break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def outerTrees(self, trees: List[List[int]]) -> List[List[int]]:\n",
    "        trees.sort()\n",
    "        n = len(trees)\n",
    "\n",
    "        if n < 4:\n",
    "            return trees\n",
    "\n",
    "        def cross(x, y, z):\n",
    "            return (y[0] - x[0]) * (z[1] - x[1]) - (y[1] - x[1]) * (z[0] - x[0])\n",
    "        \n",
    "        used = [False] * n\n",
    "        stk = [0]\n",
    "\n",
    "        n = len(trees)\n",
    "        for i in range(1, n):\n",
    "            while len(stk) > 1 and cross(trees[stk[-2]], trees[stk[-1]], trees[i]) < 0:\n",
    "                used[stk.pop()] = False\n",
    "            used[i] = True\n",
    "            stk.append(i)\n",
    "        m = len(stk)\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            if used[i]:\n",
    "                continue\n",
    "            while len(stk) > m and cross(trees[stk[-2]], trees[stk[-1]], trees[i]) < 0:\n",
    "                used[stk.pop()] = False\n",
    "            used[i] = True\n",
    "            stk.append(i)\n",
    "        stk.pop()\n",
    "        return [trees[i] for i in stk]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def cross(vector1, vector2):\n",
    "    return vector1[0] * vector2[1] - vector2[0] * vector1[1]\n",
    "\n",
    "def check(point1, point2, point3):\n",
    "    vector1 = (point2[0] - point1[0]), (point2[1] - point1[1])\n",
    "    vector2 = (point3[0] - point2[0]), (point3[1] - point2[1])\n",
    "    return cross(vector1, vector2)\n",
    "\n",
    "def convex(points):\n",
    "    hull = []\n",
    "    idx = sorted(range(len(points)), key=lambda x:points[x])\n",
    "    points = [points[i] for i in idx]\n",
    "    for i in range(len(points)):\n",
    "        while len(hull) > 1 and check(points[hull[-2]], points[hull[-1]], points[i]) < 0: hull.pop()\n",
    "        if i not in hull: hull.append(i)\n",
    "    for i in reversed(range(len(points))):\n",
    "        while len(hull) > 1 and check(points[hull[-2]], points[hull[-1]], points[i]) < 0: hull.pop()\n",
    "        if i not in hull: hull.append(i)\n",
    "    return [idx[i] for i in hull]\n",
    "\n",
    "class Solution:\n",
    "    def outerTrees(self, trees):\n",
    "        return [trees[i] for i in convex(trees)]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def outerTrees(self, trees: List[List[int]]) -> List[List[int]]:\r\n",
    "        def cross(p,q,r):\r\n",
    "            return (q[0]-p[0])*(r[1]-q[1])-(q[1]-p[1])*(r[0]-q[0])\r\n",
    "        if len(trees)<4:\r\n",
    "            return trees\r\n",
    "        leftMost=0\r\n",
    "        for i in range(1,len(trees)):\r\n",
    "            if trees[i][0]<trees[leftMost][0] or (trees[i][0]==trees[leftMost][0] and trees[i][1]<trees[leftMost][1]):\r\n",
    "                leftMost=i\r\n",
    "        \r\n",
    "        p=leftMost\r\n",
    "        vis=[False]*len(trees)\r\n",
    "        ans=[]\r\n",
    "        while True:\r\n",
    "            q=(p+1)%len(trees)\r\n",
    "            for r in range(len(trees)):\r\n",
    "                if cross(trees[p],trees[q],trees[r])<0:\r\n",
    "                    q=r\r\n",
    "            for i in range(len(trees)):\r\n",
    "                if vis[i] or i==q or i==p:\r\n",
    "                    continue\r\n",
    "                if cross(trees[p],trees[q],trees[i])==0:\r\n",
    "                    ans.append(trees[i])\r\n",
    "                    vis[i]=True\r\n",
    "            if not vis[q]:\r\n",
    "                ans.append(trees[q])\r\n",
    "                vis[q]=True\r\n",
    "            p=q\r\n",
    "            if p==leftMost:\r\n",
    "                break\r\n",
    "        return ans\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def outerTrees(self, trees: List[List[int]]) -> List[List[int]]:\n",
    "        def cross(p: List[int], q: List[int], r: List[int]) -> int:\n",
    "            return (q[0] - p[0]) * (r[1] - q[1]) - (q[1] - p[1]) * (r[0] - q[0])\n",
    "        \n",
    "        def distance(p: List[int], q: List[int]) -> int:\n",
    "            return (p[0] - q[0]) ** 2 + (p[1] - q[1]) ** 2\n",
    "        \n",
    "        n = len(trees)\n",
    "        if n < 4:\n",
    "            return trees\n",
    "        \n",
    "        bottom = 0\n",
    "        for i, tree in enumerate(trees):\n",
    "            if tree[1] < trees[bottom][1]:\n",
    "                bottom = i\n",
    "        trees[bottom], trees[0] = trees[0], trees[bottom]\n",
    "\n",
    "        def cmp(lhs: List[int], rhs: List[int]) -> int:\n",
    "            diff = -cross(trees[0], lhs, rhs)\n",
    "            return diff if diff else distance(trees[0], lhs) - distance(trees[0], rhs)\n",
    "        \n",
    "        trees[1:] = sorted(trees[1:], key=cmp_to_key(cmp))\n",
    "\n",
    "        r = n - 1\n",
    "        while r >= 0 and cross(trees[0], trees[n - 1], trees[r]) == 0:\n",
    "            r -= 1\n",
    "        l, h = r + 1, n - 1\n",
    "        while l < h:\n",
    "            trees[l], trees[h] = trees[h], trees[l]\n",
    "            l += 1\n",
    "            h -= 1\n",
    "        \n",
    "        stack = [0, 1]\n",
    "        for i in range(2, n):\n",
    "            while len(stack) > 1 and cross(trees[stack[-2]], trees[stack[-1]], trees[i]) < 0:\n",
    "                stack.pop()\n",
    "            stack.append(i)\n",
    "        return [trees[i] for i in stack]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def outerTrees(self, trees: List[List[int]]) -> List[List[int]]:\n",
    "        def cross(p, q, r):\n",
    "            return (q[0] - p[0]) * (r[1] - q[1]) - (q[1] - p[1]) * (r[0] - q[0])\n",
    "\n",
    "        n = len(trees)\n",
    "        if n < 4:\n",
    "            return trees\n",
    "\n",
    "        leftMost = 0\n",
    "        for i, tree in enumerate(trees):\n",
    "            if tree[0] < trees[leftMost][0] or (tree[0] == trees[leftMost][0] and tree[1] < trees[leftMost][1]):\n",
    "                leftMost = i\n",
    "\n",
    "        ans = []\n",
    "        vis = [False] * n\n",
    "        p = leftMost\n",
    "        while True:\n",
    "            q = (p + 1) % n\n",
    "            for r, tree in enumerate(trees):\n",
    "                # // 如果 r 在 pq 的右侧，则 q = r\n",
    "                if cross(trees[p], trees[q], tree) < 0:\n",
    "                    q = r\n",
    "            # 是否存在点 i, 使得 p q i 在同一条直线上\n",
    "            for i, b in enumerate(vis):\n",
    "                if not b and i != p and i != q and cross(trees[p], trees[q], trees[i]) == 0:\n",
    "                    ans.append(trees[i])\n",
    "                    vis[i] = True\n",
    "            if not vis[q]:\n",
    "                ans.append(trees[q])\n",
    "                vis[q] = True\n",
    "            p = q\n",
    "            if p == leftMost:\n",
    "                break\n",
    "        return sorted(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def outerTrees(self, trees: List[List[int]]) -> List[List[int]]:\n",
    "        def cross(p: List[int], q: List[int], r: List[int]) -> int:\n",
    "            return (q[0] - p[0]) * (r[1] - q[1]) - (q[1] - p[1]) * (r[0] - q[0])\n",
    "\n",
    "        def distance(p: List[int], q: List[int]) -> int:\n",
    "            return (p[0] - q[0]) * (p[0] - q[0]) + (p[1] - q[1]) * (p[1] - q[1])\n",
    "\n",
    "        n = len(trees)\n",
    "        if n < 4:\n",
    "            return trees\n",
    "\n",
    "        # 找到 y 最小的点 bottom\n",
    "        bottom = 0\n",
    "        for i, tree in enumerate(trees):\n",
    "            if tree[1] < trees[bottom][1]:\n",
    "                bottom = i\n",
    "        trees[bottom], trees[0] = trees[0], trees[bottom]\n",
    "\n",
    "        # 以 bottom 原点，按照极坐标的角度大小进行排序\n",
    "        def cmp(a: List[int], b: List[int]) -> int:\n",
    "            diff = - cross(trees[0], a, b)\n",
    "            return diff if diff else distance(trees[0], a) - distance(trees[0], b)\n",
    "        trees[1:] = sorted(trees[1:], key=cmp_to_key(cmp))\n",
    "\n",
    "        # 对于凸包最后且在同一条直线的元素按照距离从大到小进行排序\n",
    "        r = n - 1\n",
    "        while r >= 0 and cross(trees[0], trees[n - 1], trees[r]) == 0:\n",
    "            r -= 1\n",
    "        l, h = r + 1, n - 1\n",
    "        while l < h:\n",
    "            trees[l], trees[h] = trees[h], trees[l]\n",
    "            l += 1\n",
    "            h -= 1\n",
    "\n",
    "        stack = [0, 1]\n",
    "        for i in range(2, n):\n",
    "            # 如果当前元素与栈顶的两个元素构成的向量顺时针旋转，则弹出栈顶元素\n",
    "            while len(stack) > 1 and cross(trees[stack[-2]], trees[stack[-1]], trees[i]) < 0:\n",
    "                stack.pop()\n",
    "            stack.append(i)\n",
    "        return [trees[i] for i in stack]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def outerTrees(self, trees: List[List[int]]) -> List[List[int]]:\n",
    "        def cross(p: List[int], q: List[int], r: List[int]) -> int:\n",
    "            return (q[0] - p[0]) * (r[1] - q[1]) - (q[1] - p[1]) * (r[0] - q[0])\n",
    "\n",
    "        def distance(p: List[int], q: List[int]) -> int:\n",
    "            return (p[0] - q[0]) * (p[0] - q[0]) + (p[1] - q[1]) * (p[1] - q[1])\n",
    "\n",
    "        n = len(trees)\n",
    "        if n < 4:\n",
    "            return trees\n",
    "\n",
    "        # 找到 y 最小的点 bottom\n",
    "        bottom = 0\n",
    "        for i, tree in enumerate(trees):\n",
    "            if tree[1] < trees[bottom][1]:\n",
    "                bottom = i\n",
    "        trees[bottom], trees[0] = trees[0], trees[bottom]\n",
    "\n",
    "        # 以 bottom 原点，按照极坐标的角度大小进行排序\n",
    "        def cmp(a: List[int], b: List[int]) -> int:\n",
    "            diff = - cross(trees[0], a, b)\n",
    "            return diff if diff else distance(trees[0], a) - distance(trees[0], b)\n",
    "        trees[1:] = sorted(trees[1:], key=cmp_to_key(cmp))\n",
    "\n",
    "        # 对于凸包最后且在同一条直线的元素按照距离从大到小进行排序\n",
    "        r = n - 1\n",
    "        while r >= 0 and cross(trees[0], trees[n - 1], trees[r]) == 0:\n",
    "            r -= 1\n",
    "        l, h = r + 1, n - 1\n",
    "        while l < h:\n",
    "            trees[l], trees[h] = trees[h], trees[l]\n",
    "            l += 1\n",
    "            h -= 1\n",
    "\n",
    "        stack = [0, 1]\n",
    "        for i in range(2, n):\n",
    "            # 如果当前元素与栈顶的两个元素构成的向量顺时针旋转，则弹出栈顶元素\n",
    "            while len(stack) > 1 and cross(trees[stack[-2]], trees[stack[-1]], trees[i]) < 0:\n",
    "                stack.pop()\n",
    "            stack.append(i)\n",
    "        return [trees[i] for i in stack]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def outerTrees(self, trees: List[List[int]]) -> List[List[int]]:\n",
    "        # 向量PQ与QR的叉积\n",
    "        def cross(p: List[int], q: List[int], r: List[int]) -> int:\n",
    "            return (q[0] - p[0]) * (r[1] - q[1]) - (q[1] - p[1]) * (r[0] - q[0])\n",
    "\n",
    "        def distance(p: List[int], q: List[int]) -> int:\n",
    "            return (p[0] - q[0]) * (p[0] - q[0]) + (p[1] - q[1]) * (p[1] - q[1])\n",
    "\n",
    "        n = len(trees)\n",
    "        if n < 4:\n",
    "            return trees\n",
    "\n",
    "        # 找到 y 最小的点 bottom\n",
    "        bottom = 0\n",
    "        for i, tree in enumerate(trees):\n",
    "            if tree[1] < trees[bottom][1]:\n",
    "                bottom = i\n",
    "        trees[bottom], trees[0] = trees[0], trees[bottom]\n",
    "\n",
    "        # 以 bottom 原点，按照极坐标的角度大小进行排序\n",
    "        def cmp(a: List[int], b: List[int]) -> int:\n",
    "            diff = - cross(trees[0], a, b)\n",
    "            return diff if diff else distance(trees[0], a) - distance(trees[0], b)\n",
    "        trees[1:] = sorted(trees[1:], key=cmp_to_key(cmp))\n",
    "\n",
    "        # 对于凸包最后且在同一条直线的元素按照距离从大到小进行排序\n",
    "        r = n - 1\n",
    "        while r >= 0 and cross(trees[0], trees[n - 1], trees[r]) == 0:\n",
    "            r -= 1\n",
    "        l, h = r + 1, n - 1\n",
    "        while l < h:\n",
    "            trees[l], trees[h] = trees[h], trees[l]\n",
    "            l += 1\n",
    "            h -= 1\n",
    "\n",
    "        stack = [0, 1]\n",
    "        for i in range(2, n):\n",
    "            # 如果当前元素与栈顶的两个元素构成的向量顺时针旋转，则弹出栈顶元素\n",
    "            while len(stack) > 1 and cross(trees[stack[-2]], trees[stack[-1]], trees[i]) < 0:\n",
    "                stack.pop()\n",
    "            stack.append(i)\n",
    "        return [trees[i] for i in stack]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def outerTrees(self, trees: List[List[int]]) -> List[List[int]]:\n",
    "        n = len(trees)\n",
    "        if n < 4: \n",
    "            return trees\n",
    "        \n",
    "        def cross(p, q, r):\n",
    "            return (q[0] - p[0]) * (r[1] - q[1]) - (q[1] - p[1]) * (r[0] - q[0])\n",
    "\n",
    "        def distance(p, q):\n",
    "            return (p[0] - q[0]) * (p[0] - q[0]) + (p[1] - q[1]) * (p[1] - q[1])\n",
    "\n",
    "        s = 0\n",
    "        for i, tree in enumerate(trees):\n",
    "            if tree[0] < trees[s][0] or tree[0] == trees[s][0] and tree[1] < trees[s][1]:\n",
    "                s = i\n",
    "        \n",
    "        trees[0], trees[s] = trees[s], trees[0]\n",
    "\n",
    "        def cmp(a, b):\n",
    "            diff = -cross(trees[0], a, b)\n",
    "            return diff if diff else distance(trees[0], a) - distance(trees[0], b)\n",
    "        \n",
    "        trees[1:] = sorted(trees[1:], key=cmp_to_key(cmp))\n",
    "\n",
    "        r = n - 1\n",
    "        while r >= 0 and cross(trees[0], trees[n - 1], trees[r]) == 0:\n",
    "            r -= 1\n",
    "        l, h = r + 1, n - 1\n",
    "        while l < h:\n",
    "            trees[l], trees[h] = trees[h], trees[l]\n",
    "            l += 1\n",
    "            h -= 1\n",
    "        \n",
    "        stack = [0, 1]\n",
    "        for i in range(2, n):\n",
    "            while len(stack) > 1 and cross(trees[stack[-2]], trees[stack[-1]], trees[i]) < 0:\n",
    "                stack.pop()\n",
    "            stack.append(i)\n",
    "        return [trees[i] for i in stack]\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 向量相减\n",
    "def substraction(a, b):\n",
    "    return [a[0] - b[0], a[1] - b[1]]\n",
    "# 叉乘\n",
    "def cross(a, b):\n",
    "    return a[0] * b[1] - a[1] * b[0]\n",
    "# 向量ab转为ac扫过的面积\n",
    "def getArea(a, b, c):\n",
    "    return cross(substraction(b, a), substraction(c, a))\n",
    "\n",
    "class Solution:\n",
    "    def outerTrees(self, trees: List[List[int]]) -> List[List[int]]:\n",
    "        trees.sort(key=lambda x: (x[0], x[1]))\n",
    "        n = len(trees)\n",
    "        tp = 0\n",
    "        stk = [0] * (n + 10)\n",
    "        vis = [False] * (n + 10)\n",
    "        tp += 1\n",
    "        stk[tp] = 0\n",
    "        for i in range(1, n):\n",
    "            c = trees[i]\n",
    "            while tp >= 2:\n",
    "                a, b = trees[stk[tp - 1]], trees[stk[tp]]\n",
    "                if getArea(a, b, c) > 0:\n",
    "                    vis[stk[tp]] = False\n",
    "                    tp -= 1\n",
    "                else:\n",
    "                    break\n",
    "            tp += 1\n",
    "            stk[tp] = i\n",
    "            vis[i] = True\n",
    "        size = tp\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            if vis[i]:\n",
    "                continue\n",
    "            c = trees[i]\n",
    "            while tp > size:\n",
    "                a, b = trees[stk[tp - 1]], trees[stk[tp]]\n",
    "                if getArea(a, b, c) > 0:\n",
    "                    tp -= 1\n",
    "                else:\n",
    "                    break\n",
    "            tp += 1\n",
    "            stk[tp] = i\n",
    "        ans = [[0] * (2) for _ in range(tp - 1)]\n",
    "        for i in range(tp):\n",
    "            ans[i - 1]  = trees[stk[i]]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def outerTrees(self, trees: List[List[int]]) -> List[List[int]]:\n",
    "        def cross(p, q, r):\n",
    "            score = (q[0] - p[0]) * (r[1] - q[1]) - (q[1] - p[1]) * (r[0] - q[0])\n",
    "            return score\n",
    "        def cal(trees):\n",
    "            n = len(trees)\n",
    "            stack, top = list([0 for _ in range(n)]), 1\n",
    "            stack[1] = 1\n",
    "            res = []\n",
    "            for i in range(2, n):\n",
    "                # print(stack[top-1], i, )\n",
    "                while top > 0 and cross(trees[stack[top-1]], trees[stack[top]], trees[i]) < 0:\n",
    "                        top -= 1\n",
    "                top += 1\n",
    "                stack[top] = i\n",
    "            return stack[:top+1]\n",
    "            \n",
    "\n",
    "        # print(stack, top)\n",
    "        if len(trees) <= 1:\n",
    "            return trees\n",
    "        trees.sort()\n",
    "        x1 = cal(trees)\n",
    "        x2 = cal([[x[0], -x[1]] for x in trees])\n",
    "        res = set(x1+x2)\n",
    "        return [trees[i] for i in res]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def outerTrees(self, trees: List[List[int]]) -> List[List[int]]:\n",
    "        def cross(p: List[int], q: List[int], r: List[int]) -> int:\n",
    "            return (q[0] - p[0]) * (r[1] - q[1]) - (q[1] - p[1]) * (r[0] - q[0])\n",
    "\n",
    "        def distance(p: List[int], q: List[int]) -> int:\n",
    "            return (p[0] - q[0]) * (p[0] - q[0]) + (p[1] - q[1]) * (p[1] - q[1])\n",
    "\n",
    "        n = len(trees)\n",
    "        if n < 4:\n",
    "            return trees\n",
    "\n",
    "        # 找到 y 最小的点 bottom\n",
    "        #[[1,1],[2,2],[2,0],[2,4],[3,3],[4,2]]\n",
    "        bottom = 0\n",
    "        # for i, tree in enumerate(trees):\n",
    "        #     if tree[1] < trees[bottom][1]:\n",
    "        #         bottom = i\n",
    "        # trees[bottom], trees[0] = trees[0], trees[bottom]\n",
    "        trees.sort(key=lambda x: x[1])\n",
    "\n",
    "        # 以 bottom 原点，按照极坐标的角度大小进行排序\n",
    "        def cmp(a: List[int], b: List[int]) -> int:\n",
    "            diff = - cross(trees[0], a, b)\n",
    "            return diff if diff else distance(trees[0], a) - distance(trees[0], b)\n",
    "        trees[1:] = sorted(trees[1:], key=cmp_to_key(cmp))\n",
    "\n",
    "        # 对于凸包最后且在同一条直线的元素按照距离从大到小进行排序\n",
    "        r = n - 1\n",
    "        while r >= 0 and cross(trees[0], trees[n - 1], trees[r]) == 0:\n",
    "            r -= 1\n",
    "        l, h = r + 1, n - 1\n",
    "        while l < h:\n",
    "            trees[l], trees[h] = trees[h], trees[l]\n",
    "            l += 1\n",
    "            h -= 1\n",
    "\n",
    "        stack = [0, 1]\n",
    "        for i in range(2, n):\n",
    "            # 如果当前元素与栈顶的两个元素构成的向量顺时针旋转，则弹出栈顶元素\n",
    "            while len(stack) > 1 and cross(trees[stack[-2]], trees[stack[-1]], trees[i]) < 0:\n",
    "                stack.pop()\n",
    "            stack.append(i)\n",
    "        return [trees[i] for i in stack]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def outerTrees(self, trees: List[List[int]]) -> List[List[int]]:\r\n",
    "        def cross(p: List[int], q: List[int], r: List[int]) -> int:\r\n",
    "            return (q[0] - p[0]) * (r[1] - q[1]) - (q[1] - p[1]) * (r[0] - q[0])\r\n",
    "\r\n",
    "        def distance(p: List[int], q: List[int]) -> int:\r\n",
    "            return (p[0] - q[0]) * (p[0] - q[0]) + (p[1] - q[1]) * (p[1] - q[1])\r\n",
    "\r\n",
    "        n = len(trees)\r\n",
    "        if n < 4:\r\n",
    "            return trees\r\n",
    "\r\n",
    "        # 找到 y 最小的点 bottom\r\n",
    "        #[[1,1],[2,2],[2,0],[2,4],[3,3],[4,2]]\r\n",
    "        bottom = 0\r\n",
    "        for i, tree in enumerate(trees):\r\n",
    "            if tree[1] < trees[bottom][1]:\r\n",
    "                bottom = i\r\n",
    "        trees[bottom], trees[0] = trees[0], trees[bottom]\r\n",
    "\r\n",
    "        # 以 bottom 原点，按照极坐标的角度大小进行排序\r\n",
    "        def cmp(a: List[int], b: List[int]) -> int:\r\n",
    "            diff = - cross(trees[0], a, b)\r\n",
    "            return diff if diff else distance(trees[0], a) - distance(trees[0], b)\r\n",
    "        trees[1:] = sorted(trees[1:], key=cmp_to_key(cmp))\r\n",
    "\r\n",
    "        # 对于凸包最后且在同一条直线的元素按照距离从大到小进行排序\r\n",
    "        r = n - 1\r\n",
    "        while r >= 0 and cross(trees[0], trees[n - 1], trees[r]) == 0:\r\n",
    "            r -= 1\r\n",
    "        l, h = r + 1, n - 1\r\n",
    "        while l < h:\r\n",
    "            trees[l], trees[h] = trees[h], trees[l]\r\n",
    "            l += 1\r\n",
    "            h -= 1\r\n",
    "\r\n",
    "        stack = [0, 1]\r\n",
    "        for i in range(2, n):\r\n",
    "            # 如果当前元素与栈顶的两个元素构成的向量顺时针旋转，则弹出栈顶元素\r\n",
    "            while len(stack) > 1 and cross(trees[stack[-2]], trees[stack[-1]], trees[i]) < 0:\r\n",
    "                stack.pop()\r\n",
    "            stack.append(i)\r\n",
    "        return [trees[i] for i in stack]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def outerTrees(self, trees: List[List[int]]) -> List[List[int]]:\n",
    "        def cross(p: List[int], q: List[int], r: List[int]) -> int:\n",
    "            return (q[0] - p[0]) * (r[1] - q[1]) - (q[1] - p[1]) * (r[0] - q[0])\n",
    "\n",
    "        def distance(p: List[int], q: List[int]) -> int:\n",
    "            return (p[0] - q[0]) * (p[0] - q[0]) + (p[1] - q[1]) * (p[1] - q[1])\n",
    "\n",
    "        n = len(trees)\n",
    "        if n < 4:\n",
    "            return trees\n",
    "\n",
    "        # 找到 y 最小的点 bottom\n",
    "        bottom = 0\n",
    "        for i, tree in enumerate(trees):\n",
    "            if tree[1] < trees[bottom][1]:\n",
    "                bottom = i\n",
    "        trees[bottom], trees[0] = trees[0], trees[bottom]\n",
    "\n",
    "        # 以 bottom 原点，按照极坐标的角度大小进行排序\n",
    "        def cmp(a: List[int], b: List[int]) -> int:\n",
    "            diff = - cross(trees[0], a, b)\n",
    "            return diff if diff else distance(trees[0], a) - distance(trees[0], b)\n",
    "        trees[1:] = sorted(trees[1:], key=cmp_to_key(cmp))\n",
    "\n",
    "        # 对于凸包最后且在同一条直线的元素按照距离从大到小进行排序\n",
    "        r = n - 1\n",
    "        while r >= 0 and cross(trees[0], trees[n - 1], trees[r]) == 0:\n",
    "            r -= 1\n",
    "        l, h = r + 1, n - 1\n",
    "        while l < h:\n",
    "            trees[l], trees[h] = trees[h], trees[l]\n",
    "            l += 1\n",
    "            h -= 1\n",
    "\n",
    "        stack = [0, 1]\n",
    "        for i in range(2, n):\n",
    "            # 如果当前元素与栈顶的两个元素构成的向量顺时针旋转，则弹出栈顶元素\n",
    "            while len(stack) > 1 and cross(trees[stack[-2]], trees[stack[-1]], trees[i]) < 0:\n",
    "                stack.pop()\n",
    "            stack.append(i)\n",
    "        return [trees[i] for i in stack]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def outerTrees(self, points: List[List[int]]) -> List[List[int]]:\n",
    "        # Sort the points lexicographically (tuples are compared lexicographically).\n",
    "        # Remove duplicates to detect the case we have just one unique point.\n",
    "        # points = sorted(set(points))\n",
    "        points = sorted(points, key=lambda p: (p[0], p[1]))\n",
    "\n",
    "        # Boring case: no points or a single point, possibly repeated multiple times.\n",
    "        if len(points) <= 1:\n",
    "            return points\n",
    "\n",
    "        # 2D cross product of OA and OB vectors, i.e. z-component of their 3D cross product.\n",
    "        # Returns a positive value, if OAB makes a counter-clockwise turn,\n",
    "        # negative for clockwise turn, and zero if the points are collinear.\n",
    "        def cross(o, a, b):\n",
    "            # return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])\n",
    "            return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])\n",
    "\n",
    "        # Build lower hull\n",
    "        lower = []\n",
    "        for p in points:\n",
    "            while len(lower) >= 2 and cross(lower[-2], lower[-1], p) < 0:\n",
    "                lower.pop()\n",
    "            lower.append(p)\n",
    "\n",
    "        # Build upper hull\n",
    "        upper = []\n",
    "        for p in reversed(points):\n",
    "            while len(upper) >= 2 and cross(upper[-2], upper[-1], p) < 0:\n",
    "                upper.pop()\n",
    "            upper.append(p)\n",
    "\n",
    "        # Concatenation of the lower and upper hulls gives the convex hull.\n",
    "        # Last point of each list is omitted because it is repeated at the\n",
    "        # beginning of the other list.\n",
    "        # return lower[:-1] + upper[:-1]\n",
    "        return list(map(list, set(map(tuple, lower[:-1] + upper[:-1]))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def r(self, p1, p2, to_detect, upper_flag, ans):\n",
    "        f_p = None\n",
    "        f_p_area = -1\n",
    "        for point in to_detect:\n",
    "            curr_area = self.calc_area(p1, p2, point)\n",
    "            if curr_area > f_p_area:\n",
    "                f_p_area = curr_area\n",
    "                f_p = point\n",
    "        ans.append(f_p)\n",
    "        p1_to_detect = []\n",
    "        p2_to_detect = []\n",
    "        for point in to_detect:\n",
    "            if point == f_p:\n",
    "                continue\n",
    "            if upper_flag:\n",
    "                if self.is_top(p1, f_p, point, True):\n",
    "                    p1_to_detect.append(point)\n",
    "                elif self.is_top(p2, f_p, point, True):\n",
    "                    p2_to_detect.append(point)\n",
    "            else:\n",
    "                if not self.is_top(p1, f_p, point, False):\n",
    "                    p1_to_detect.append(point)\n",
    "                elif not self.is_top(p2, f_p, point, False):\n",
    "                    p2_to_detect.append(point)\n",
    "        if p1_to_detect:\n",
    "            self.r(p1, f_p, p1_to_detect, upper_flag, ans)\n",
    "        if p2_to_detect:\n",
    "            self.r(p2, f_p, p2_to_detect, upper_flag, ans)\n",
    "        return\n",
    "\n",
    "    def is_top(self, p1, p2, p3, count_on):\n",
    "        x1, y1 = p1\n",
    "        x2, y2 = p2\n",
    "        x3, y3 = p3\n",
    "        if x1 == x2:\n",
    "            return (x3 <= x1) if count_on else (x3 < x1)\n",
    "        elif y1 == y2:\n",
    "            return (y3 >= y1) if count_on else (y3 > y1)\n",
    "        else:\n",
    "            a = y2 - y1\n",
    "            b = x1 - x2\n",
    "            c = x2 * y1 - x1 * y2\n",
    "            if b < 0:\n",
    "                a, b, c = a * -1, b * -1, c * -1\n",
    "            return (a * x3 + b * y3 + c >= 0) if count_on else (a * x3 + b * y3 + c > 0)\n",
    "\n",
    "    def calc_area(self, p1, p2, p3):\n",
    "        (x1, y1), (x2, y2), (x3, y3) = p1, p2, p3\n",
    "        return 0.5 * abs(x2 * y3 + x1 * y2 + x3 * y1 - x3 * y2 - x2 * y1 - x1 * y3)\n",
    "\n",
    "    def outerTrees(self, trees: List[List[int]]) -> List[List[int]]:\n",
    "        n = len(trees)\n",
    "        if n <= 3:\n",
    "            return trees\n",
    "        trees.sort(key=lambda coord: (coord[0], coord[1]))\n",
    "        ans = [trees[0], trees[-1]]\n",
    "        upper = []\n",
    "        lower = []\n",
    "        on_boundary = []\n",
    "        for i in range(1, n - 1):\n",
    "            if self.is_top(trees[0], trees[-1], trees[i], False):\n",
    "                upper.append(trees[i])\n",
    "            elif not self.is_top(trees[0], trees[-1], trees[i], True):\n",
    "                lower.append(trees[i])\n",
    "            else:\n",
    "                on_boundary.append(trees[i])\n",
    "        if not upper or not lower:\n",
    "            for point in on_boundary:\n",
    "                ans.append(point)\n",
    "        if upper:\n",
    "            self.r(trees[0], trees[-1], upper, True, ans)\n",
    "        if lower:\n",
    "            self.r(trees[0], trees[-1], lower, False, ans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 递归，每次利用凸包多边形中点集中的两个点\n",
    "    # 当upper_flag为True则说明本次运行是一次上半凸包求解，否则是一次下半凸包求解\n",
    "    # 参数k是用于调整print的log的格式的，即递归深度\n",
    "    def r(self, p1, p2, to_detect, upper_flag, ans, k=0):\n",
    "        # 找到最远点, f指furthest\n",
    "        f_p = None\n",
    "        f_p_area = -1\n",
    "        for point in to_detect:\n",
    "            curr_area = self.calc_area(p1, p2, point)\n",
    "            if curr_area > f_p_area:\n",
    "                f_p_area = curr_area\n",
    "                f_p = point\n",
    "        # print(f'{\"|   \" * k}p1: {p1}\\tp2: {p2}\\tf_p: {f_p} | mode: {upper_flag} | to_detect: {to_detect}')\n",
    "        ans.append(f_p)\n",
    "\n",
    "        # 分割新的子上半凸包和子下半凸包\n",
    "        p1_to_detect = []\n",
    "        p2_to_detect = []\n",
    "        for point in to_detect:\n",
    "            if point == f_p:\n",
    "                continue\n",
    "            if upper_flag:\n",
    "                # 在直线 p1, f_p 上方和恰在其上的点要继续考虑\n",
    "                if self.is_top(p1, f_p, point, True):\n",
    "                    p1_to_detect.append(point)\n",
    "                    # print(f'{\"|   \" * k}{point} at p1 upper, add to p1_to_detect')\n",
    "                # 在直线 p2, f_p 上方和恰在其上的点要继续考虑\n",
    "                elif self.is_top(p2, f_p, point, True):\n",
    "                    p2_to_detect.append(point)\n",
    "                    # print(f'{\"|   \" * k}{point} at p2 upper, add to p2_to_detect')\n",
    "                # 其他的点不可能是凸包点集的成员\n",
    "                # else:\n",
    "                #     print(f'{\"|   \" * k}{point} abandoned')\n",
    "                #     pass\n",
    "            else:\n",
    "                # 在直线 p1, f_p 下方和恰在其上的点要继续考虑\n",
    "                if not self.is_top(p1, f_p, point, False):\n",
    "                    p1_to_detect.append(point)\n",
    "                    # print(f'{\"|   \" * k}{point} at p1 lower, add to p1_to_detect')\n",
    "                # 在直线 p2, f_p 下方和恰在其上的点要继续考虑\n",
    "                elif not self.is_top(p2, f_p, point, False):\n",
    "                    p2_to_detect.append(point)\n",
    "                    # print(f'{\"|   \" * k}{point} at p2 lower, add to p1_to_detect')\n",
    "                # 其他的点不可能是凸包点集的成员\n",
    "                # else:\n",
    "                #     print(f'{\"|   \" * k}{point} abandoned')\n",
    "                #     pass\n",
    "        if p1_to_detect:\n",
    "            self.r(p1, f_p, p1_to_detect, upper_flag, ans, k + 1)\n",
    "        if p2_to_detect:\n",
    "            self.r(p2, f_p, p2_to_detect, upper_flag, ans, k + 1)\n",
    "        return\n",
    "\n",
    "    # 判断p3是在p1,p2构成直线的上方\n",
    "    # 上方的定义：直线方程ax + by + c = 0\n",
    "    #   1. b != 0 时，直线方程变形至b大于0， ax + by + c > 0则在上方\n",
    "    #   2. b == 0 时，直线方程为ax + c = 0，则直线的左侧视为上方\n",
    "    # 特殊地，当设置 count_on=True 时，那么恰在直线上的点也视为在上方\n",
    "    def is_top(self, p1, p2, p3, count_on):\n",
    "        x1, y1 = p1\n",
    "        x2, y2 = p2\n",
    "        x3, y3 = p3\n",
    "        if x1 == x2:\n",
    "            # 此时直线方程为 x - x1 = 0\n",
    "            return (x3 <= x1) if count_on else (x3 < x1)\n",
    "        elif y1 == y2:\n",
    "            # 此时直线方程为 y - y1 = 0\n",
    "            return (y3 >= y1) if count_on else (y3 > y1)\n",
    "        else:\n",
    "            # 此时直线有非零斜率\n",
    "            a = y2 - y1\n",
    "            b = x1 - x2\n",
    "            c = x2 * y1 - x1 * y2\n",
    "            if b < 0:\n",
    "                a, b, c = a * -1, b * -1, c * -1\n",
    "            return (a * x3 + b * y3 + c >= 0) if count_on else (a * x3 + b * y3 + c > 0)\n",
    "\n",
    "    # 从三点坐标计算围出的三角形面积\n",
    "    # 原理是求两向量平行四边形的面积的一半\n",
    "    # 然后手工推一下行列式化简\n",
    "    def calc_area(self, p1, p2, p3):\n",
    "        (x1, y1), (x2, y2), (x3, y3) = p1, p2, p3\n",
    "        return 0.5 * abs(x2 * y3 + x1 * y2 + x3 * y1 - x3 * y2 - x2 * y1 - x1 * y3)\n",
    "\n",
    "    def outerTrees(self, trees: List[List[int]]) -> List[List[int]]:\n",
    "        n = len(trees)\n",
    "\n",
    "        # 简单剪枝\n",
    "        if n <= 3:\n",
    "            return trees\n",
    "\n",
    "        # 使用quickhull算法\n",
    "\n",
    "        # 将所有点按照x升序排列，如果x相等则按照y升序排列\n",
    "        trees.sort(key=lambda coord: (coord[0], coord[1]))\n",
    "\n",
    "        # 凸包点集，首末点一定在凸包多边形点集中\n",
    "        ans = [trees[0], trees[-1]]\n",
    "\n",
    "        # 待测点集\n",
    "        upper = []\n",
    "        lower = []\n",
    "        # 边界点集\n",
    "        on_boundary = []\n",
    "\n",
    "        for i in range(1, n - 1):\n",
    "            if self.is_top(trees[0], trees[-1], trees[i], False):\n",
    "                upper.append(trees[i])\n",
    "            elif not self.is_top(trees[0], trees[-1], trees[i], True):\n",
    "                lower.append(trees[i])\n",
    "            else:\n",
    "                on_boundary.append(trees[i])\n",
    "\n",
    "        # 为什么需要单独考虑边界：\n",
    "        #   因为第一次划分是二叉的，而后面的递归实际上是三叉，只是其中一叉是被抛弃的点集子树\n",
    "        if not upper or not lower:\n",
    "            for point in on_boundary:\n",
    "                ans.append(point)\n",
    "\n",
    "        if upper:\n",
    "            self.r(trees[0], trees[-1], upper, True, ans)\n",
    "        if lower:\n",
    "            self.r(trees[0], trees[-1], lower, False, ans)\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def r(self, p1, p2, to_detect, upper_flag, ans):\n",
    "        f_p = None\n",
    "        f_p_area = -1\n",
    "        for point in to_detect:\n",
    "            curr_area = self.calc_area(p1, p2, point)\n",
    "            if curr_area > f_p_area:\n",
    "                f_p_area = curr_area\n",
    "                f_p = point\n",
    "        ans.append(f_p)\n",
    "        p1_to_detect = []\n",
    "        p2_to_detect = []\n",
    "        for point in to_detect:\n",
    "            if point == f_p:\n",
    "                continue\n",
    "            if upper_flag:\n",
    "                if self.is_top(p1, f_p, point, True):\n",
    "                    p1_to_detect.append(point)\n",
    "                elif self.is_top(p2, f_p, point, True):\n",
    "                    p2_to_detect.append(point)\n",
    "            else:\n",
    "                if not self.is_top(p1, f_p, point, False):\n",
    "                    p1_to_detect.append(point)\n",
    "                elif not self.is_top(p2, f_p, point, False):\n",
    "                    p2_to_detect.append(point)\n",
    "        if p1_to_detect:\n",
    "            self.r(p1, f_p, p1_to_detect, upper_flag, ans)\n",
    "        if p2_to_detect:\n",
    "            self.r(p2, f_p, p2_to_detect, upper_flag, ans)\n",
    "        return\n",
    "    def is_top(self, p1, p2, p3, count_on):\n",
    "        x1, y1 = p1\n",
    "        x2, y2 = p2\n",
    "        x3, y3 = p3\n",
    "        if x1 == x2:\n",
    "            return (x3 <= x1) if count_on else (x3 < x1)\n",
    "        elif y1 == y2:\n",
    "            return (y3 >= y1) if count_on else (y3 > y1)\n",
    "        else:\n",
    "            a = y2 - y1\n",
    "            b = x1 - x2\n",
    "            c = x2 * y1 - x1 * y2\n",
    "            if b < 0:\n",
    "                a, b, c = a * -1, b * -1, c * -1\n",
    "            return (a * x3 + b * y3 + c >= 0) if count_on else (a * x3 + b * y3 + c > 0)\n",
    "    def calc_area(self, p1, p2, p3):\n",
    "        (x1, y1), (x2, y2), (x3, y3) = p1, p2, p3\n",
    "        return 0.5 * abs(x2 * y3 + x1 * y2 + x3 * y1 - x3 * y2 - x2 * y1 - x1 * y3)\n",
    "\n",
    "    def outerTrees(self, trees: List[List[int]]) -> List[List[int]]:\n",
    "        n = len(trees)\n",
    "        if n <= 3:\n",
    "            return trees\n",
    "        trees.sort(key=lambda coord: (coord[0], coord[1]))\n",
    "        ans = [trees[0], trees[-1]]\n",
    "        upper = []\n",
    "        lower = []\n",
    "        on_boundary = []\n",
    "\n",
    "        for i in range(1, n - 1):\n",
    "            if self.is_top(trees[0], trees[-1], trees[i], False):\n",
    "                upper.append(trees[i])\n",
    "            elif not self.is_top(trees[0], trees[-1], trees[i], True):\n",
    "                lower.append(trees[i])\n",
    "            else:\n",
    "                on_boundary.append(trees[i])\n",
    "        if not upper or not lower:\n",
    "            for point in on_boundary:\n",
    "                ans.append(point)\n",
    "\n",
    "        if upper:\n",
    "            self.r(trees[0], trees[-1], upper, True, ans)\n",
    "        if lower:\n",
    "            self.r(trees[0], trees[-1], lower, False, ans)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def r(self, p1, p2, to_detect, upper_flag, ans):\n",
    "        f_p = None\n",
    "        f_p_area = -1\n",
    "        for point in to_detect:\n",
    "            curr_area = self.calc_area(p1, p2, point)\n",
    "            if curr_area > f_p_area:\n",
    "                f_p_area = curr_area\n",
    "                f_p = point\n",
    "        ans.append(f_p)\n",
    "        p1_to_detect = []\n",
    "        p2_to_detect = []\n",
    "        for point in to_detect:\n",
    "            if point == f_p:\n",
    "                continue\n",
    "            if upper_flag:\n",
    "                if self.is_top(p1, f_p, point, True):\n",
    "                    p1_to_detect.append(point)\n",
    "                elif self.is_top(p2, f_p, point, True):\n",
    "                    p2_to_detect.append(point)\n",
    "            else:\n",
    "                if not self.is_top(p1, f_p, point, False):\n",
    "                    p1_to_detect.append(point)\n",
    "                elif not self.is_top(p2, f_p, point, False):\n",
    "                    p2_to_detect.append(point)\n",
    "        if p1_to_detect:\n",
    "            self.r(p1, f_p, p1_to_detect, upper_flag, ans)\n",
    "        if p2_to_detect:\n",
    "            self.r(p2, f_p, p2_to_detect, upper_flag, ans)\n",
    "        return\n",
    "    def is_top(self, p1, p2, p3, count_on):\n",
    "        x1, y1 = p1\n",
    "        x2, y2 = p2\n",
    "        x3, y3 = p3\n",
    "        if x1 == x2:\n",
    "            return (x3 <= x1) if count_on else (x3 < x1)\n",
    "        elif y1 == y2:\n",
    "            return (y3 >= y1) if count_on else (y3 > y1)\n",
    "        else:\n",
    "            a = y2 - y1\n",
    "            b = x1 - x2\n",
    "            c = x2 * y1 - x1 * y2\n",
    "            if b < 0:\n",
    "                a, b, c = a * -1, b * -1, c * -1\n",
    "            return (a * x3 + b * y3 + c >= 0) if count_on else (a * x3 + b * y3 + c > 0)\n",
    "    def calc_area(self, p1, p2, p3):\n",
    "        (x1, y1), (x2, y2), (x3, y3) = p1, p2, p3\n",
    "        return 0.5 * abs(x2 * y3 + x1 * y2 + x3 * y1 - x3 * y2 - x2 * y1 - x1 * y3)\n",
    "\n",
    "    def outerTrees(self, trees: List[List[int]]) -> List[List[int]]:\n",
    "        n = len(trees)\n",
    "        if n <= 3:\n",
    "            return trees\n",
    "        trees.sort(key=lambda coord: (coord[0], coord[1]))\n",
    "        ans = [trees[0], trees[-1]]\n",
    "        upper = []\n",
    "        lower = []\n",
    "        on_boundary = []\n",
    "\n",
    "        for i in range(1, n - 1):\n",
    "            if self.is_top(trees[0], trees[-1], trees[i], False):\n",
    "                upper.append(trees[i])\n",
    "            elif not self.is_top(trees[0], trees[-1], trees[i], True):\n",
    "                lower.append(trees[i])\n",
    "            else:\n",
    "                on_boundary.append(trees[i])\n",
    "        if not upper or not lower:\n",
    "            for point in on_boundary:\n",
    "                ans.append(point)\n",
    "\n",
    "        if upper:\n",
    "            self.r(trees[0], trees[-1], upper, True, ans)\n",
    "        if lower:\n",
    "            self.r(trees[0], trees[-1], lower, False, ans)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 递归，每次利用凸包多边形中点集中的两个点\n",
    "    # 当upper_flag为True则说明本次运行是一次上半凸包求解，否则是一次下半凸包求解\n",
    "    # 参数k是用于调整print的log的格式的，即递归深度\n",
    "    def r(self, p1, p2, to_detect, upper_flag, ans, k=0):\n",
    "        # 找到最远点, f指furthest\n",
    "        f_p = None\n",
    "        f_p_area = -1\n",
    "        for point in to_detect:\n",
    "            curr_area = self.calc_area(p1, p2, point)\n",
    "            if curr_area > f_p_area:\n",
    "                f_p_area = curr_area\n",
    "                f_p = point\n",
    "        # print(f'{\"|   \" * k}p1: {p1}\\tp2: {p2}\\tf_p: {f_p} | mode: {upper_flag} | to_detect: {to_detect}')\n",
    "        ans.append(f_p)\n",
    "\n",
    "        # 分割新的子上半凸包和子下半凸包\n",
    "        p1_to_detect = []\n",
    "        p2_to_detect = []\n",
    "        for point in to_detect:\n",
    "            if point == f_p:\n",
    "                continue\n",
    "            if upper_flag:\n",
    "                # 在直线 p1, f_p 上方和恰在其上的点要继续考虑\n",
    "                if self.is_top(p1, f_p, point, True):\n",
    "                    p1_to_detect.append(point)\n",
    "                    # print(f'{\"|   \" * k}{point} at p1 upper, add to p1_to_detect')\n",
    "                # 在直线 p2, f_p 上方和恰在其上的点要继续考虑\n",
    "                elif self.is_top(p2, f_p, point, True):\n",
    "                    p2_to_detect.append(point)\n",
    "                    # print(f'{\"|   \" * k}{point} at p2 upper, add to p2_to_detect')\n",
    "                # 其他的点不可能是凸包点集的成员\n",
    "                # else:\n",
    "                #     print(f'{\"|   \" * k}{point} abandoned')\n",
    "                #     pass\n",
    "            else:\n",
    "                # 在直线 p1, f_p 下方和恰在其上的点要继续考虑\n",
    "                if not self.is_top(p1, f_p, point, False):\n",
    "                    p1_to_detect.append(point)\n",
    "                    # print(f'{\"|   \" * k}{point} at p1 lower, add to p1_to_detect')\n",
    "                # 在直线 p2, f_p 下方和恰在其上的点要继续考虑\n",
    "                elif not self.is_top(p2, f_p, point, False):\n",
    "                    p2_to_detect.append(point)\n",
    "                    # print(f'{\"|   \" * k}{point} at p2 lower, add to p1_to_detect')\n",
    "                # 其他的点不可能是凸包点集的成员\n",
    "                # else:\n",
    "                #     print(f'{\"|   \" * k}{point} abandoned')\n",
    "                #     pass\n",
    "        if p1_to_detect:\n",
    "            self.r(p1, f_p, p1_to_detect, upper_flag, ans, k + 1)\n",
    "        if p2_to_detect:\n",
    "            self.r(p2, f_p, p2_to_detect, upper_flag, ans, k + 1)\n",
    "        return\n",
    "\n",
    "    # 判断p3是在p1,p2构成直线的上方\n",
    "    # 上方的定义：直线方程ax + by + c = 0\n",
    "    #   1. b != 0 时，直线方程变形至b大于0， ax + by + c > 0则在上方\n",
    "    #   2. b == 0 时，直线方程为ax + c = 0，则直线的左侧视为上方\n",
    "    # 特殊地，当设置 count_on=True 时，那么恰在直线上的点也视为在上方\n",
    "    def is_top(self, p1, p2, p3, count_on):\n",
    "        x1, y1 = p1\n",
    "        x2, y2 = p2\n",
    "        x3, y3 = p3\n",
    "        if x1 == x2:\n",
    "            # 此时直线方程为 x - x1 = 0\n",
    "            return (x3 <= x1) if count_on else (x3 < x1)\n",
    "        elif y1 == y2:\n",
    "            # 此时直线方程为 y - y1 = 0\n",
    "            return (y3 >= y1) if count_on else (y3 > y1)\n",
    "        else:\n",
    "            # 此时直线有非零斜率\n",
    "            a = y2 - y1\n",
    "            b = x1 - x2\n",
    "            c = x2 * y1 - x1 * y2\n",
    "            if b < 0:\n",
    "                a, b, c = a * -1, b * -1, c * -1\n",
    "            return (a * x3 + b * y3 + c >= 0) if count_on else (a * x3 + b * y3 + c > 0)\n",
    "\n",
    "    # 从三点坐标计算围出的三角形面积\n",
    "    # 原理是求两向量平行四边形的面积的一半\n",
    "    # 然后手工推一下行列式化简\n",
    "    def calc_area(self, p1, p2, p3):\n",
    "        (x1, y1), (x2, y2), (x3, y3) = p1, p2, p3\n",
    "        return 0.5 * abs(x2 * y3 + x1 * y2 + x3 * y1 - x3 * y2 - x2 * y1 - x1 * y3)\n",
    "\n",
    "    def outerTrees(self, trees: List[List[int]]) -> List[List[int]]:\n",
    "        n = len(trees)\n",
    "\n",
    "        # 简单剪枝\n",
    "        if n <= 3:\n",
    "            return trees\n",
    "\n",
    "        # 使用quickhull算法\n",
    "\n",
    "        # 将所有点按照x升序排列，如果x相等则按照y升序排列\n",
    "        trees.sort(key=lambda coord: (coord[0], coord[1]))\n",
    "\n",
    "        # 凸包点集，首末点一定在凸包多边形点集中\n",
    "        ans = [trees[0], trees[-1]]\n",
    "\n",
    "        # 待测点集\n",
    "        upper = []\n",
    "        lower = []\n",
    "        # 边界点集\n",
    "        on_boundary = []\n",
    "\n",
    "        for i in range(1, n - 1):\n",
    "            if self.is_top(trees[0], trees[-1], trees[i], False):\n",
    "                upper.append(trees[i])\n",
    "            elif not self.is_top(trees[0], trees[-1], trees[i], True):\n",
    "                lower.append(trees[i])\n",
    "            else:\n",
    "                on_boundary.append(trees[i])\n",
    "\n",
    "        # 为什么需要单独考虑边界：\n",
    "        #   因为第一次划分是二叉的，而后面的递归实际上是三叉，只是其中一叉是被抛弃的点集子树\n",
    "        if not upper or not lower:\n",
    "            for point in on_boundary:\n",
    "                ans.append(point)\n",
    "\n",
    "        if upper:\n",
    "            self.r(trees[0], trees[-1], upper, True, ans)\n",
    "        if lower:\n",
    "            self.r(trees[0], trees[-1], lower, False, ans)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def r(self, p1, p2, to_detect, upper_flag, ans):\n",
    "        f_p = None\n",
    "        f_p_area = -1\n",
    "        for point in to_detect:\n",
    "            curr_area = self.calc_area(p1, p2, point)\n",
    "            if curr_area > f_p_area:\n",
    "                f_p_area = curr_area\n",
    "                f_p = point\n",
    "        ans.append(f_p)\n",
    "        p1_to_detect = []\n",
    "        p2_to_detect = []\n",
    "        for point in to_detect:\n",
    "            if point == f_p:\n",
    "                continue\n",
    "            if upper_flag:\n",
    "                if self.is_top(p1, f_p, point, True):\n",
    "                    p1_to_detect.append(point)\n",
    "                elif self.is_top(p2, f_p, point, True):\n",
    "                    p2_to_detect.append(point)\n",
    "            else:\n",
    "                if not self.is_top(p1, f_p, point, False):\n",
    "                    p1_to_detect.append(point)\n",
    "                elif not self.is_top(p2, f_p, point, False):\n",
    "                    p2_to_detect.append(point)\n",
    "        if p1_to_detect:\n",
    "            self.r(p1, f_p, p1_to_detect, upper_flag, ans)\n",
    "        if p2_to_detect:\n",
    "            self.r(p2, f_p, p2_to_detect, upper_flag, ans)\n",
    "        return\n",
    "\n",
    "    def is_top(self, p1, p2, p3, count_on):\n",
    "        x1, y1 = p1\n",
    "        x2, y2 = p2\n",
    "        x3, y3 = p3\n",
    "        if x1 == x2:\n",
    "            return (x3 <= x1) if count_on else (x3 < x1)\n",
    "        elif y1 == y2:\n",
    "            return (y3 >= y1) if count_on else (y3 > y1)\n",
    "        else:\n",
    "            a = y2 - y1\n",
    "            b = x1 - x2\n",
    "            c = x2 * y1 - x1 * y2\n",
    "            if b < 0:\n",
    "                a, b, c = a * -1, b * -1, c * -1\n",
    "            return (a * x3 + b * y3 + c >= 0) if count_on else (a * x3 + b * y3 + c > 0)\n",
    "\n",
    "    def calc_area(self, p1, p2, p3):\n",
    "        (x1, y1), (x2, y2), (x3, y3) = p1, p2, p3\n",
    "        return 0.5 * abs(x2 * y3 + x1 * y2 + x3 * y1 - x3 * y2 - x2 * y1 - x1 * y3)\n",
    "\n",
    "    def outerTrees(self, trees: List[List[int]]) -> List[List[int]]:\n",
    "        n = len(trees)\n",
    "        if n <= 3:\n",
    "            return trees\n",
    "        trees.sort(key=lambda coord: (coord[0], coord[1]))\n",
    "        ans = [trees[0], trees[-1]]\n",
    "        upper = []\n",
    "        lower = []\n",
    "        on_boundary = []\n",
    "        for i in range(1, n - 1):\n",
    "            if self.is_top(trees[0], trees[-1], trees[i], False):\n",
    "                upper.append(trees[i])\n",
    "            elif not self.is_top(trees[0], trees[-1], trees[i], True):\n",
    "                lower.append(trees[i])\n",
    "            else:\n",
    "                on_boundary.append(trees[i])\n",
    "        if not upper or not lower:\n",
    "            for point in on_boundary:\n",
    "                ans.append(point)\n",
    "        if upper:\n",
    "            self.r(trees[0], trees[-1], upper, True, ans)\n",
    "        if lower:\n",
    "            self.r(trees[0], trees[-1], lower, False, ans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def r(self, p1, p2, to_detect, upper_flag, ans):\n",
    "        f_p = None\n",
    "        f_p_area = -1\n",
    "        for point in to_detect:\n",
    "            curr_area = self.calc_area(p1, p2, point)\n",
    "            if curr_area > f_p_area:\n",
    "                f_p_area = curr_area\n",
    "                f_p = point\n",
    "        ans.append(f_p)\n",
    "        p1_to_detect = []\n",
    "        p2_to_detect = []\n",
    "        for point in to_detect:\n",
    "            if point == f_p:\n",
    "                continue\n",
    "            if upper_flag:\n",
    "                if self.is_top(p1, f_p, point, True):\n",
    "                    p1_to_detect.append(point)\n",
    "                elif self.is_top(p2, f_p, point, True):\n",
    "                    p2_to_detect.append(point)\n",
    "            else:\n",
    "                if not self.is_top(p1, f_p, point, False):\n",
    "                    p1_to_detect.append(point)\n",
    "                elif not self.is_top(p2, f_p, point, False):\n",
    "                    p2_to_detect.append(point)\n",
    "        if p1_to_detect:\n",
    "            self.r(p1, f_p, p1_to_detect, upper_flag, ans)\n",
    "        if p2_to_detect:\n",
    "            self.r(p2, f_p, p2_to_detect, upper_flag, ans)\n",
    "        return\n",
    "    def is_top(self, p1, p2, p3, count_on):\n",
    "        x1, y1 = p1\n",
    "        x2, y2 = p2\n",
    "        x3, y3 = p3\n",
    "        if x1 == x2:\n",
    "            return (x3 <= x1) if count_on else (x3 < x1)\n",
    "        elif y1 == y2:\n",
    "            return (y3 >= y1) if count_on else (y3 > y1)\n",
    "        else:\n",
    "            a = y2 - y1\n",
    "            b = x1 - x2\n",
    "            c = x2 * y1 - x1 * y2\n",
    "            if b < 0:\n",
    "                a, b, c = a * -1, b * -1, c * -1\n",
    "            return (a * x3 + b * y3 + c >= 0) if count_on else (a * x3 + b * y3 + c > 0)\n",
    "    def calc_area(self, p1, p2, p3):\n",
    "        (x1, y1), (x2, y2), (x3, y3) = p1, p2, p3\n",
    "        return 0.5 * abs(x2 * y3 + x1 * y2 + x3 * y1 - x3 * y2 - x2 * y1 - x1 * y3)\n",
    "\n",
    "    def outerTrees(self, trees: List[List[int]]) -> List[List[int]]:\n",
    "        n = len(trees)\n",
    "\n",
    "        if n <= 3:\n",
    "            return trees\n",
    "\n",
    "        # 使用quickhull算法\n",
    "\n",
    "        # 将所有点按照x升序排列，如果x相等则按照y升序排列\n",
    "        trees.sort(key=lambda coord: (coord[0], coord[1]))\n",
    "\n",
    "        # 凸包点集，首末点一定在凸包多边形点集中\n",
    "        ans = [trees[0], trees[-1]]\n",
    "\n",
    "        # 待测点集\n",
    "        upper = []\n",
    "        lower = []\n",
    "        # 边界点集\n",
    "        on_boundary = []\n",
    "\n",
    "        for i in range(1, n - 1):\n",
    "            if self.is_top(trees[0], trees[-1], trees[i], False):\n",
    "                upper.append(trees[i])\n",
    "            elif not self.is_top(trees[0], trees[-1], trees[i], True):\n",
    "                lower.append(trees[i])\n",
    "            else:\n",
    "                on_boundary.append(trees[i])\n",
    "\n",
    "        # 为什么需要单独考虑边界：\n",
    "        #   因为第一次划分是二叉的，而后面的递归实际上是三叉，只是其中一叉是被抛弃的点集子树\n",
    "        if not upper or not lower:\n",
    "            for point in on_boundary:\n",
    "                ans.append(point)\n",
    "\n",
    "        if upper:\n",
    "            self.r(trees[0], trees[-1], upper, True, ans)\n",
    "        if lower:\n",
    "            self.r(trees[0], trees[-1], lower, False, ans)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 递归，每次利用凸包多边形中点集中的两个点\n",
    "    # 当upper_flag为True则说明本次运行是一次上半凸包求解，否则是一次下半凸包求解\n",
    "    # 参数k是用于调整print的log的格式的，即递归深度\n",
    "    def r(self, p1, p2, to_detect, upper_flag, ans, k=0):\n",
    "        # 找到最远点, f指furthest\n",
    "        f_p = None\n",
    "        f_p_area = -1\n",
    "        for point in to_detect:\n",
    "            curr_area = self.calc_area(p1, p2, point)\n",
    "            if curr_area > f_p_area:\n",
    "                f_p_area = curr_area\n",
    "                f_p = point\n",
    "        # print(f'{\"|   \" * k}p1: {p1}\\tp2: {p2}\\tf_p: {f_p} | mode: {upper_flag} | to_detect: {to_detect}')\n",
    "        ans.append(f_p)\n",
    "\n",
    "        # 分割新的子上半凸包和子下半凸包\n",
    "        p1_to_detect = []\n",
    "        p2_to_detect = []\n",
    "        for point in to_detect:\n",
    "            if point == f_p:\n",
    "                continue\n",
    "            if upper_flag:\n",
    "                # 在直线 p1, f_p 上方和恰在其上的点要继续考虑\n",
    "                if self.is_top(p1, f_p, point, True):\n",
    "                    p1_to_detect.append(point)\n",
    "                    # print(f'{\"|   \" * k}{point} at p1 upper, add to p1_to_detect')\n",
    "                # 在直线 p2, f_p 上方和恰在其上的点要继续考虑\n",
    "                elif self.is_top(p2, f_p, point, True):\n",
    "                    p2_to_detect.append(point)\n",
    "                    # print(f'{\"|   \" * k}{point} at p2 upper, add to p2_to_detect')\n",
    "                # 其他的点不可能是凸包点集的成员\n",
    "                # else:\n",
    "                #     print(f'{\"|   \" * k}{point} abandoned')\n",
    "                #     pass\n",
    "            else:\n",
    "                # 在直线 p1, f_p 下方和恰在其上的点要继续考虑\n",
    "                if not self.is_top(p1, f_p, point, False):\n",
    "                    p1_to_detect.append(point)\n",
    "                    # print(f'{\"|   \" * k}{point} at p1 lower, add to p1_to_detect')\n",
    "                # 在直线 p2, f_p 下方和恰在其上的点要继续考虑\n",
    "                elif not self.is_top(p2, f_p, point, False):\n",
    "                    p2_to_detect.append(point)\n",
    "                    # print(f'{\"|   \" * k}{point} at p2 lower, add to p1_to_detect')\n",
    "                # 其他的点不可能是凸包点集的成员\n",
    "                # else:\n",
    "                #     print(f'{\"|   \" * k}{point} abandoned')\n",
    "                #     pass\n",
    "        if p1_to_detect:\n",
    "            self.r(p1, f_p, p1_to_detect, upper_flag, ans, k + 1)\n",
    "        if p2_to_detect:\n",
    "            self.r(p2, f_p, p2_to_detect, upper_flag, ans, k + 1)\n",
    "        return\n",
    "\n",
    "    # 判断p3是在p1,p2构成直线的上方\n",
    "    # 上方的定义：直线方程ax + by + c = 0\n",
    "    #   1. b != 0 时，直线方程变形至b大于0， ax + by + c > 0则在上方\n",
    "    #   2. b == 0 时，直线方程为ax + c = 0，则直线的左侧视为上方\n",
    "    # 特殊地，当设置 count_on=True 时，那么恰在直线上的点也视为在上方\n",
    "    def is_top(self, p1, p2, p3, count_on):\n",
    "        x1, y1 = p1\n",
    "        x2, y2 = p2\n",
    "        x3, y3 = p3\n",
    "        if x1 == x2:\n",
    "            # 此时直线方程为 x - x1 = 0\n",
    "            return (x3 <= x1) if count_on else (x3 < x1)\n",
    "        elif y1 == y2:\n",
    "            # 此时直线方程为 y - y1 = 0\n",
    "            return (y3 >= y1) if count_on else (y3 > y1)\n",
    "        else:\n",
    "            # 此时直线有非零斜率\n",
    "            a = y2 - y1\n",
    "            b = x1 - x2\n",
    "            c = x2 * y1 - x1 * y2\n",
    "            if b < 0:\n",
    "                a, b, c = a * -1, b * -1, c * -1\n",
    "            return (a * x3 + b * y3 + c >= 0) if count_on else (a * x3 + b * y3 + c > 0)\n",
    "\n",
    "    # 从三点坐标计算围出的三角形面积\n",
    "    # 原理是求两向量平行四边形的面积的一半\n",
    "    # 然后手工推一下行列式化简\n",
    "    def calc_area(self, p1, p2, p3):\n",
    "        (x1, y1), (x2, y2), (x3, y3) = p1, p2, p3\n",
    "        return 0.5 * abs(x2 * y3 + x1 * y2 + x3 * y1 - x3 * y2 - x2 * y1 - x1 * y3)\n",
    "\n",
    "    def outerTrees(self, trees: List[List[int]]) -> List[List[int]]:\n",
    "        n = len(trees)\n",
    "\n",
    "        # 简单剪枝\n",
    "        if n <= 3:\n",
    "            return trees\n",
    "\n",
    "        # 使用quickhull算法\n",
    "\n",
    "        # 将所有点按照x升序排列，如果x相等则按照y升序排列\n",
    "        trees.sort(key=lambda coord: (coord[0], coord[1]))\n",
    "\n",
    "        # 凸包点集，首末点一定在凸包多边形点集中\n",
    "        ans = [trees[0], trees[-1]]\n",
    "\n",
    "        # 待测点集\n",
    "        upper = []\n",
    "        lower = []\n",
    "        # 边界点集\n",
    "        on_boundary = []\n",
    "\n",
    "        for i in range(1, n - 1):\n",
    "            if self.is_top(trees[0], trees[-1], trees[i], False):\n",
    "                upper.append(trees[i])\n",
    "            elif not self.is_top(trees[0], trees[-1], trees[i], True):\n",
    "                lower.append(trees[i])\n",
    "            else:\n",
    "                on_boundary.append(trees[i])\n",
    "\n",
    "        # 为什么需要单独考虑边界：\n",
    "        #   因为第一次划分是二叉的，而后面的递归实际上是三叉，只是其中一叉是被抛弃的点集子树\n",
    "        if not upper or not lower:\n",
    "            for point in on_boundary:\n",
    "                ans.append(point)\n",
    "\n",
    "        if upper:\n",
    "            self.r(trees[0], trees[-1], upper, True, ans)\n",
    "        if lower:\n",
    "            self.r(trees[0], trees[-1], lower, False, ans)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def outerTrees(self, trees: List[List[int]]) -> List[List[int]]:\n",
    "        trees.sort()\n",
    "        x, y = trees.pop(0)\n",
    "        t = {}\n",
    "        for x1, y1 in trees:\n",
    "            if x1 == x:\n",
    "                n = 101\n",
    "            else:\n",
    "                n = (y1 - y) / (x1 - x)\n",
    "            if n not in t:\n",
    "                t[n] = []\n",
    "            t[n].append([x1, y1])\n",
    "                        \n",
    "        def findIntersection(x1, y1, x2, y2, x3, y3, x4, y4):\n",
    "            px= ((x1 * y2 - y1 * x2) * (x3 - x4) - (x1 - x2) * (x3 * y4 - y3 * x4) ) / ( (x1 - x2) * (y3 - y4) - (y1 - y2) * (x3 - x4)) \n",
    "            py= ((x1 * y2 - y1 * x2) * (y3 - y4) - (y1 - y2) * (x3 * y4 - y3 * x4) ) / ( (x1 - x2) * (y3 - y4) - (y1 - y2) * (x3 - x4))\n",
    "            return [px, py]\n",
    "\n",
    "        def dis(x1, y1, x2, y2):\n",
    "            return (y1 - y2) ** 2 + (x1 - x2) ** 2\n",
    "\n",
    "        def IsPop(m, n, x1, y1, x2, y2):\n",
    "            a, b = findIntersection(x, y, m, n, x1, y1, x2, y2)\n",
    "            return dis(m, n, x, y) < dis(a, b, x, y)\n",
    "            \n",
    "        res = [[[x, y]]]\n",
    "        for k in sorted(t.keys()):\n",
    "            p = t[k]\n",
    "            if len(res) < 2:\n",
    "                res.append(p)\n",
    "            else:\n",
    "                while len(res) > 2 and IsPop(res[-1][-1][0], res[-1][-1][1], p[-1][0], p[-1][1], res[-2][-1][0], res[-2][-1][1]):\n",
    "                    res.pop(-1)\n",
    "                if len(res) > 2:\n",
    "                    res[-1] = [res[-1][-1]]\n",
    "                res.append(p)\n",
    "        return sum(res,[])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def r(self, p1, p2, to_detect, upper_flag, ans):\n",
    "        f_p = None\n",
    "        f_p_area = -1\n",
    "        for point in to_detect:\n",
    "            curr_area = self.calc_area(p1, p2, point)\n",
    "            if curr_area > f_p_area:\n",
    "                f_p_area = curr_area\n",
    "                f_p = point\n",
    "        ans.append(f_p)\n",
    "        p1_to_detect = []\n",
    "        p2_to_detect = []\n",
    "        for point in to_detect:\n",
    "            if point == f_p:\n",
    "                continue\n",
    "            if upper_flag:\n",
    "                if self.is_top(p1, f_p, point, True):\n",
    "                    p1_to_detect.append(point)\n",
    "                elif self.is_top(p2, f_p, point, True):\n",
    "                    p2_to_detect.append(point)\n",
    "            else:\n",
    "                if not self.is_top(p1, f_p, point, False):\n",
    "                    p1_to_detect.append(point)\n",
    "                elif not self.is_top(p2, f_p, point, False):\n",
    "                    p2_to_detect.append(point)\n",
    "        if p1_to_detect:\n",
    "            self.r(p1, f_p, p1_to_detect, upper_flag, ans)\n",
    "        if p2_to_detect:\n",
    "            self.r(p2, f_p, p2_to_detect, upper_flag, ans)\n",
    "        return\n",
    "    def is_top(self, p1, p2, p3, count_on):\n",
    "        x1, y1 = p1\n",
    "        x2, y2 = p2\n",
    "        x3, y3 = p3\n",
    "        if x1 == x2:\n",
    "            return (x3 <= x1) if count_on else (x3 < x1)\n",
    "        elif y1 == y2:\n",
    "            return (y3 >= y1) if count_on else (y3 > y1)\n",
    "        else:\n",
    "            a = y2 - y1\n",
    "            b = x1 - x2\n",
    "            c = x2 * y1 - x1 * y2\n",
    "            if b < 0:\n",
    "                a, b, c = a * -1, b * -1, c * -1\n",
    "            return (a * x3 + b * y3 + c >= 0) if count_on else (a * x3 + b * y3 + c > 0)\n",
    "    def calc_area(self, p1, p2, p3):\n",
    "        (x1, y1), (x2, y2), (x3, y3) = p1, p2, p3\n",
    "        return 0.5 * abs(x2 * y3 + x1 * y2 + x3 * y1 - x3 * y2 - x2 * y1 - x1 * y3)\n",
    "\n",
    "    def outerTrees(self, trees: List[List[int]]) -> List[List[int]]:\n",
    "        n = len(trees)\n",
    "        if n <= 3:\n",
    "            return trees\n",
    "        trees.sort(key=lambda coord: (coord[0], coord[1]))\n",
    "        ans = [trees[0], trees[-1]]\n",
    "        upper = []\n",
    "        lower = []\n",
    "        on_boundary = []\n",
    "\n",
    "        for i in range(1, n - 1):\n",
    "            if self.is_top(trees[0], trees[-1], trees[i], False):\n",
    "                upper.append(trees[i])\n",
    "            elif not self.is_top(trees[0], trees[-1], trees[i], True):\n",
    "                lower.append(trees[i])\n",
    "            else:\n",
    "                on_boundary.append(trees[i])\n",
    "        if not upper or not lower:\n",
    "            for point in on_boundary:\n",
    "                ans.append(point)\n",
    "\n",
    "        if upper:\n",
    "            self.r(trees[0], trees[-1], upper, True, ans)\n",
    "        if lower:\n",
    "            self.r(trees[0], trees[-1], lower, False, ans)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 递归，每次利用凸包多边形中点集中的两个点\n",
    "    # 当upper_flag为True则说明本次运行是一次上半凸包求解，否则是一次下半凸包求解\n",
    "    # 参数k是用于调整print的log的格式的，即递归深度\n",
    "    def r(self, p1, p2, to_detect, upper_flag, ans, k=0):\n",
    "        # 找到最远点, f指furthest\n",
    "        f_p = None\n",
    "        f_p_area = -1\n",
    "        for point in to_detect:\n",
    "            curr_area = self.calc_area(p1, p2, point)\n",
    "            if curr_area > f_p_area:\n",
    "                f_p_area = curr_area\n",
    "                f_p = point\n",
    "        # print(f'{\"|   \" * k}p1: {p1}\\tp2: {p2}\\tf_p: {f_p} | mode: {upper_flag} | to_detect: {to_detect}')\n",
    "        ans.append(f_p)\n",
    "\n",
    "        # 分割新的子上半凸包和子下半凸包\n",
    "        p1_to_detect = []\n",
    "        p2_to_detect = []\n",
    "        for point in to_detect:\n",
    "            if point == f_p:\n",
    "                continue\n",
    "            if upper_flag:\n",
    "                # 在直线 p1, f_p 上方和恰在其上的点要继续考虑\n",
    "                if self.is_top(p1, f_p, point, True):\n",
    "                    p1_to_detect.append(point)\n",
    "                    # print(f'{\"|   \" * k}{point} at p1 upper, add to p1_to_detect')\n",
    "                # 在直线 p2, f_p 上方和恰在其上的点要继续考虑\n",
    "                elif self.is_top(p2, f_p, point, True):\n",
    "                    p2_to_detect.append(point)\n",
    "                    # print(f'{\"|   \" * k}{point} at p2 upper, add to p2_to_detect')\n",
    "                # 其他的点不可能是凸包点集的成员\n",
    "                # else:\n",
    "                #     print(f'{\"|   \" * k}{point} abandoned')\n",
    "                #     pass\n",
    "            else:\n",
    "                # 在直线 p1, f_p 下方和恰在其上的点要继续考虑\n",
    "                if not self.is_top(p1, f_p, point, False):\n",
    "                    p1_to_detect.append(point)\n",
    "                    # print(f'{\"|   \" * k}{point} at p1 lower, add to p1_to_detect')\n",
    "                # 在直线 p2, f_p 下方和恰在其上的点要继续考虑\n",
    "                elif not self.is_top(p2, f_p, point, False):\n",
    "                    p2_to_detect.append(point)\n",
    "                    # print(f'{\"|   \" * k}{point} at p2 lower, add to p1_to_detect')\n",
    "                # 其他的点不可能是凸包点集的成员\n",
    "                # else:\n",
    "                #     print(f'{\"|   \" * k}{point} abandoned')\n",
    "                #     pass\n",
    "        if p1_to_detect:\n",
    "            self.r(p1, f_p, p1_to_detect, upper_flag, ans, k + 1)\n",
    "        if p2_to_detect:\n",
    "            self.r(p2, f_p, p2_to_detect, upper_flag, ans, k + 1)\n",
    "        return\n",
    "\n",
    "    # 判断p3是在p1,p2构成直线的上方\n",
    "    # 上方的定义：直线方程ax + by + c = 0\n",
    "    #   1. b != 0 时，直线方程变形至b大于0， ax + by + c > 0则在上方\n",
    "    #   2. b == 0 时，直线方程为ax + c = 0，则直线的左侧视为上方\n",
    "    # 特殊地，当设置 count_on=True 时，那么恰在直线上的点也视为在上方\n",
    "    def is_top(self, p1, p2, p3, count_on):\n",
    "        x1, y1 = p1\n",
    "        x2, y2 = p2\n",
    "        x3, y3 = p3\n",
    "        if x1 == x2:\n",
    "            # 此时直线方程为 x - x1 = 0\n",
    "            return (x3 <= x1) if count_on else (x3 < x1)\n",
    "        elif y1 == y2:\n",
    "            # 此时直线方程为 y - y1 = 0\n",
    "            return (y3 >= y1) if count_on else (y3 > y1)\n",
    "        else:\n",
    "            # 此时直线有非零斜率\n",
    "            a = y2 - y1\n",
    "            b = x1 - x2\n",
    "            c = x2 * y1 - x1 * y2\n",
    "            if b < 0:\n",
    "                a, b, c = a * -1, b * -1, c * -1\n",
    "            return (a * x3 + b * y3 + c >= 0) if count_on else (a * x3 + b * y3 + c > 0)\n",
    "\n",
    "    # 从三点坐标计算围出的三角形面积\n",
    "    # 原理是求两向量平行四边形的面积的一半\n",
    "    # 然后手工推一下行列式化简\n",
    "    def calc_area(self, p1, p2, p3):\n",
    "        (x1, y1), (x2, y2), (x3, y3) = p1, p2, p3\n",
    "        return 0.5 * abs(x2 * y3 + x1 * y2 + x3 * y1 - x3 * y2 - x2 * y1 - x1 * y3)\n",
    "\n",
    "    def outerTrees(self, trees: List[List[int]]) -> List[List[int]]:\n",
    "        n = len(trees)\n",
    "\n",
    "        # 简单剪枝\n",
    "        if n <= 3:\n",
    "            return trees\n",
    "\n",
    "        # 使用quickhull算法\n",
    "\n",
    "        # 将所有点按照x升序排列，如果x相等则按照y升序排列\n",
    "        trees.sort(key=lambda coord: (coord[0], coord[1]))\n",
    "\n",
    "        # 凸包点集，首末点一定在凸包多边形点集中\n",
    "        ans = [trees[0], trees[-1]]\n",
    "\n",
    "        # 待测点集\n",
    "        upper = []\n",
    "        lower = []\n",
    "        # 边界点集\n",
    "        on_boundary = []\n",
    "\n",
    "        for i in range(1, n - 1):\n",
    "            if self.is_top(trees[0], trees[-1], trees[i], False):\n",
    "                upper.append(trees[i])\n",
    "            elif not self.is_top(trees[0], trees[-1], trees[i], True):\n",
    "                lower.append(trees[i])\n",
    "            else:\n",
    "                on_boundary.append(trees[i])\n",
    "\n",
    "        # 为什么需要单独考虑边界：\n",
    "        #   因为第一次划分是二叉的，而后面的递归实际上是三叉，只是其中一叉是被抛弃的点集子树\n",
    "        if not upper or not lower:\n",
    "            for point in on_boundary:\n",
    "                ans.append(point)\n",
    "\n",
    "        if upper:\n",
    "            self.r(trees[0], trees[-1], upper, True, ans)\n",
    "        if lower:\n",
    "            self.r(trees[0], trees[-1], lower, False, ans)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 递归，每次利用凸包多边形中点集中的两个点\n",
    "    # 当upper_flag为True则说明本次运行是一次上半凸包求解，否则是一次下半凸包求解\n",
    "    # 参数k是用于调整print的log的格式的，即递归深度\n",
    "    def r(self, p1, p2, to_detect, upper_flag, ans, k=0):\n",
    "        # 找到最远点, f指furthest\n",
    "        f_p = None\n",
    "        f_p_area = -1\n",
    "        for point in to_detect:\n",
    "            curr_area = self.calc_area(p1, p2, point)\n",
    "            if curr_area > f_p_area:\n",
    "                f_p_area = curr_area\n",
    "                f_p = point\n",
    "        # print(f'{\"|   \" * k}p1: {p1}\\tp2: {p2}\\tf_p: {f_p} | mode: {upper_flag} | to_detect: {to_detect}')\n",
    "        ans.append(f_p)\n",
    "\n",
    "        # 分割新的子上半凸包和子下半凸包\n",
    "        p1_to_detect = []\n",
    "        p2_to_detect = []\n",
    "        for point in to_detect:\n",
    "            if point == f_p:\n",
    "                continue\n",
    "            if upper_flag:\n",
    "                # 在直线 p1, f_p 上方和恰在其上的点要继续考虑\n",
    "                if self.is_top(p1, f_p, point, True):\n",
    "                    p1_to_detect.append(point)\n",
    "                    # print(f'{\"|   \" * k}{point} at p1 upper, add to p1_to_detect')\n",
    "                # 在直线 p2, f_p 上方和恰在其上的点要继续考虑\n",
    "                elif self.is_top(p2, f_p, point, True):\n",
    "                    p2_to_detect.append(point)\n",
    "                    # print(f'{\"|   \" * k}{point} at p2 upper, add to p2_to_detect')\n",
    "                # 其他的点不可能是凸包点集的成员\n",
    "                # else:\n",
    "                #     print(f'{\"|   \" * k}{point} abandoned')\n",
    "                #     pass\n",
    "            else:\n",
    "                # 在直线 p1, f_p 下方和恰在其上的点要继续考虑\n",
    "                if not self.is_top(p1, f_p, point, False):\n",
    "                    p1_to_detect.append(point)\n",
    "                    # print(f'{\"|   \" * k}{point} at p1 lower, add to p1_to_detect')\n",
    "                # 在直线 p2, f_p 下方和恰在其上的点要继续考虑\n",
    "                elif not self.is_top(p2, f_p, point, False):\n",
    "                    p2_to_detect.append(point)\n",
    "                    # print(f'{\"|   \" * k}{point} at p2 lower, add to p1_to_detect')\n",
    "                # 其他的点不可能是凸包点集的成员\n",
    "                # else:\n",
    "                #     print(f'{\"|   \" * k}{point} abandoned')\n",
    "                #     pass\n",
    "        if p1_to_detect:\n",
    "            self.r(p1, f_p, p1_to_detect, upper_flag, ans, k + 1)\n",
    "        if p2_to_detect:\n",
    "            self.r(p2, f_p, p2_to_detect, upper_flag, ans, k + 1)\n",
    "        return\n",
    "\n",
    "    # 判断p3是在p1,p2构成直线的上方\n",
    "    # 上方的定义：直线方程ax + by + c = 0\n",
    "    #   1. b != 0 时，直线方程变形至b大于0， ax + by + c > 0则在上方\n",
    "    #   2. b == 0 时，直线方程为ax + c = 0，则直线的左侧视为上方\n",
    "    # 特殊地，当设置 count_on=True 时，那么恰在直线上的点也视为在上方\n",
    "    def is_top(self, p1, p2, p3, count_on):\n",
    "        x1, y1 = p1\n",
    "        x2, y2 = p2\n",
    "        x3, y3 = p3\n",
    "        if x1 == x2:\n",
    "            # 此时直线方程为 x - x1 = 0\n",
    "            return (x3 <= x1) if count_on else (x3 < x1)\n",
    "        elif y1 == y2:\n",
    "            # 此时直线方程为 y - y1 = 0\n",
    "            return (y3 >= y1) if count_on else (y3 > y1)\n",
    "        else:\n",
    "            # 此时直线有非零斜率\n",
    "            a = y2 - y1\n",
    "            b = x1 - x2\n",
    "            c = x2 * y1 - x1 * y2\n",
    "            if b < 0:\n",
    "                a, b, c = a * -1, b * -1, c * -1\n",
    "            return (a * x3 + b * y3 + c >= 0) if count_on else (a * x3 + b * y3 + c > 0)\n",
    "\n",
    "    # 从三点坐标计算围出的三角形面积\n",
    "    # 原理是求两向量平行四边形的面积的一半\n",
    "    # 然后手工推一下行列式化简\n",
    "    def calc_area(self, p1, p2, p3):\n",
    "        (x1, y1), (x2, y2), (x3, y3) = p1, p2, p3\n",
    "        return 0.5 * abs(x2 * y3 + x1 * y2 + x3 * y1 - x3 * y2 - x2 * y1 - x1 * y3)\n",
    "\n",
    "    def outerTrees(self, trees: List[List[int]]) -> List[List[int]]:\n",
    "        n = len(trees)\n",
    "\n",
    "        # 简单剪枝\n",
    "        if n <= 3:\n",
    "            return trees\n",
    "\n",
    "        # 使用quickhull算法\n",
    "\n",
    "        # 将所有点按照x升序排列，如果x相等则按照y升序排列\n",
    "        trees.sort(key=lambda coord: (coord[0], coord[1]))\n",
    "\n",
    "        # 凸包点集，首末点一定在凸包多边形点集中\n",
    "        ans = [trees[0], trees[-1]]\n",
    "\n",
    "        # 待测点集\n",
    "        upper = []\n",
    "        lower = []\n",
    "        # 边界点集\n",
    "        on_boundary = []\n",
    "\n",
    "        for i in range(1, n - 1):\n",
    "            if self.is_top(trees[0], trees[-1], trees[i], False):\n",
    "                upper.append(trees[i])\n",
    "            elif not self.is_top(trees[0], trees[-1], trees[i], True):\n",
    "                lower.append(trees[i])\n",
    "            else:\n",
    "                on_boundary.append(trees[i])\n",
    "\n",
    "        # 为什么需要单独考虑边界：\n",
    "        #   因为第一次划分是二叉的，而后面的递归实际上是三叉，只是其中一叉是被抛弃的点集子树\n",
    "        if not upper or not lower:\n",
    "            for point in on_boundary:\n",
    "                ans.append(point)\n",
    "\n",
    "        if upper:\n",
    "            self.r(trees[0], trees[-1], upper, True, ans)\n",
    "        if lower:\n",
    "            self.r(trees[0], trees[-1], lower, False, ans)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "def outer_trees(trees):\n",
    "    n = len(trees)\n",
    "    if n < 4:\n",
    "        return trees\n",
    "\n",
    "    # 排序先找到那个最左下方的点\n",
    "    trees.sort()\n",
    "    base = trees[0]\n",
    "    # 以这个点为基准算出其他点的角度\n",
    "    store = []  # 第一个存角度， 第二个存序号\n",
    "    for i in range(1, n):\n",
    "        x, y = trees[i]\n",
    "        store.append((math.atan2(y - base[1], x - base[0]), i))\n",
    "    # 按角度排序\n",
    "    store.sort()\n",
    "        # 对于凸包最后且在同一条直线的元素按照距离从大到小进行排序\n",
    "    r = n - 2\n",
    "    while r >= 0 and cross(trees[0], trees[store[n - 2][1]], trees[store[r][1]]) == 0:\n",
    "        r -= 1\n",
    "    l, h = r + 1, n - 2\n",
    "    while l < h:\n",
    "        trees[store[l][1]], trees[store[h][1]] = trees[store[h][1]], trees[store[l][1]]\n",
    "        l += 1\n",
    "        h -= 1\n",
    "    # 开始遍历填入\n",
    "    res = [0]\n",
    "    for i in range(n-1):\n",
    "        while len(res) >= 2 and cross(trees[res[-2]], trees[res[-1]], trees[store[i][1]]) < 0:\n",
    "            res.pop()\n",
    "        res.append(store[i][1])\n",
    "\n",
    "    return [trees[i] for i in res]\n",
    "\n",
    "# 三个点判断是左拐还是右拐\n",
    "def cross(p, q, r):\n",
    "    return (q[0] - p[0]) * (r[1] - q[1]) - (q[1] - p[1]) * (r[0] - q[0])\n",
    "\n",
    "class Solution:\n",
    "    def outerTrees(self, trees: List[List[int]]) -> List[List[int]]:\n",
    "        return outer_trees(trees)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy\n",
    "\n",
    "def cross(point1, point2, point3):\n",
    "    x1y2 = (point2[0] - point1[0]) * (point3[1] - point2[1])\n",
    "    x2y1 = (point3[0] - point2[0]) * (point2[1] - point1[1])\n",
    "    return x1y2 - x2y1\n",
    "\n",
    "def convex(data):\n",
    "    hull = []\n",
    "    data.sort()\n",
    "    for i in range(len(data)):\n",
    "        while len(hull) > 1 and cross(data[hull[-2]], data[hull[-1]], data[i]) < 0:\n",
    "            hull.pop()\n",
    "        hull.append(i)\n",
    "    for i in reversed(range(len(data))):\n",
    "        while len(hull) > 1 and cross(data[hull[-2]], data[hull[-1]], data[i]) < 0:\n",
    "            hull.pop()\n",
    "        hull.append(i)\n",
    "\n",
    "    return [data[i] for i in set(hull)]\n",
    "\n",
    "class Solution:\n",
    "    def outerTrees(self, trees):\n",
    "        return convex(trees)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy\n",
    "\n",
    "# def cross(point1, point2, point3):\n",
    "#     # return numpy.cross(point2 - point1, point3 - point2)\n",
    "#     vector1 = point2 - point1\n",
    "#     vector2 = point3 - point2\n",
    "#     return vector1[0] * vector2[1] - vector1[1] * vector2[0]\n",
    "\n",
    "def cross(p: List[int], q: List[int], r: List[int]) -> int:\n",
    "            return (q[0] - p[0]) * (r[1] - q[1]) - (q[1] - p[1]) * (r[0] - q[0])\n",
    "\n",
    "def convex(data):\n",
    "    hull = []\n",
    "    # numpy.lexsort(data)\n",
    "    for i in range(len(data)):\n",
    "        while len(hull) > 1 and cross(data[hull[-2]], data[hull[-1]], data[i]) < 0:\n",
    "            hull.pop()\n",
    "        hull.append(i)\n",
    "    for i in reversed(range(len(data))):\n",
    "        while len(hull) > 1 and cross(data[hull[-2]], data[hull[-1]], data[i]) < 0:\n",
    "            hull.pop()\n",
    "        hull.append(i)\n",
    "\n",
    "    return data[list(set(hull))]\n",
    "\n",
    "class Solution:\n",
    "    def outerTrees(self, trees):\n",
    "        trees.sort()\n",
    "        return convex(numpy.array(trees)).tolist()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy\n",
    "\n",
    "def cross(point1, point2, point3):\n",
    "    # return numpy.cross(point2 - point1, point3 - point2)\n",
    "    vector1 = point2 - point1\n",
    "    vector2 = point3 - point2\n",
    "    return vector1[0] * vector2[1] - vector1[1] * vector2[0]\n",
    "\n",
    "def convex(data):\n",
    "    hull = []\n",
    "    # numpy.lexsort(data)\n",
    "    for i in range(len(data)):\n",
    "        while len(hull) > 1 and cross(data[hull[-2]], data[hull[-1]], data[i]) < 0:\n",
    "            hull.pop()\n",
    "        hull.append(i)\n",
    "    for i in reversed(range(len(data))):\n",
    "        while len(hull) > 1 and cross(data[hull[-2]], data[hull[-1]], data[i]) < 0:\n",
    "            hull.pop()\n",
    "        hull.append(i)\n",
    "\n",
    "    return data[list(set(hull))]\n",
    "\n",
    "class Solution:\n",
    "    def outerTrees(self, trees):\n",
    "        trees.sort()\n",
    "        return convex(numpy.array(trees)).tolist()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy\n",
    "\n",
    "def cross(point1, point2, point3):\n",
    "    return numpy.cross(point2 - point1, point3 - point2)\n",
    "\n",
    "def convex(data):\n",
    "    hull = []\n",
    "    # numpy.lexsort(data)\n",
    "    for i in range(len(data)):\n",
    "        while len(hull) > 1 and cross(data[hull[-2]], data[hull[-1]], data[i]) < 0:\n",
    "            hull.pop()\n",
    "        hull.append(i)\n",
    "    for i in reversed(range(len(data))):\n",
    "        while len(hull) > 1 and cross(data[hull[-2]], data[hull[-1]], data[i]) < 0:\n",
    "            hull.pop()\n",
    "        hull.append(i)\n",
    "\n",
    "    return data[list(set(hull))]\n",
    "\n",
    "class Solution:\n",
    "    def outerTrees(self, trees):\n",
    "        trees.sort()\n",
    "        return convex(numpy.array(trees)).tolist()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy\n",
    "\n",
    "def cross(point1, point2, point3):\n",
    "    return numpy.cross(point2 - point1, point3 - point2)\n",
    "\n",
    "def convex(data):\n",
    "    hull = []\n",
    "    # numpy.lexsort(data)\n",
    "    for i in range(len(data)):\n",
    "        while len(hull) > 1 and cross(data[hull[-2]], data[hull[-1]], data[i]) < 0:\n",
    "            hull.pop()\n",
    "        hull.append(i)\n",
    "    for i in reversed(range(len(data))):\n",
    "        while len(hull) > 1 and cross(data[hull[-2]], data[hull[-1]], data[i]) < 0:\n",
    "            hull.pop()\n",
    "        hull.append(i)\n",
    "\n",
    "    return data[list(set(hull))]\n",
    "\n",
    "class Solution:\n",
    "    def outerTrees(self, trees):\n",
    "        trees.sort()\n",
    "        return convex(numpy.array(trees)).tolist()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy\n",
    "\n",
    "def cross(point1, point2, point3):\n",
    "    vector1 = point2 - point1\n",
    "    vector2 = point3 - point2\n",
    "    return vector1[0] * vector2[1] - vector1[1] * vector2[0]\n",
    "\n",
    "def convex(data):\n",
    "    hull = []\n",
    "    index = numpy.lexsort([data[:, 1], data[:, 0]])\n",
    "    data = data[index]\n",
    "    for i in range(len(data)):\n",
    "        while len(hull) > 1 and cross(data[hull[-2]], data[hull[-1]], data[i]) < 0:\n",
    "            hull.pop()\n",
    "        hull.append(i)\n",
    "    for i in reversed(range(len(data))):\n",
    "        while len(hull) > 1 and cross(data[hull[-2]], data[hull[-1]], data[i]) < 0:\n",
    "            hull.pop()\n",
    "        hull.append(i)\n",
    "\n",
    "    return data[list(set(hull))]\n",
    "\n",
    "class Solution:\n",
    "    def outerTrees(self, trees):\n",
    "        # trees.sort()\n",
    "        return convex(numpy.array(trees)).tolist()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy\n",
    "\n",
    "def cross(point1, point2, point3):\n",
    "    vector1 = point2 - point1\n",
    "    vector2 = point3 - point2\n",
    "    return vector1[0] * vector2[1] - vector1[1] * vector2[0]\n",
    "\n",
    "def convex(data):\n",
    "    hull = []\n",
    "    # numpy.lexsort(data)\n",
    "    for i in range(len(data)):\n",
    "        while len(hull) > 1 and cross(data[hull[-2]], data[hull[-1]], data[i]) < 0:\n",
    "            hull.pop()\n",
    "        hull.append(i)\n",
    "    for i in reversed(range(len(data))):\n",
    "        while len(hull) > 1 and cross(data[hull[-2]], data[hull[-1]], data[i]) < 0:\n",
    "            hull.pop()\n",
    "        hull.append(i)\n",
    "\n",
    "    return data[list(set(hull))]\n",
    "\n",
    "class Solution:\n",
    "    def outerTrees(self, trees):\n",
    "        trees.sort()\n",
    "        return convex(numpy.array(trees)).tolist()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy\n",
    "\n",
    "def cross(point1, point2, point3):\n",
    "    return numpy.cross(point2 - point1, point3 - point2)\n",
    "    # vector1 = point2 - point1\n",
    "    # vector2 = point3 - point2\n",
    "    # return vector1[0] * vector2[1] - vector1[1] * vector2[0]\n",
    "\n",
    "def convex(data):\n",
    "    hull = []\n",
    "    # numpy.lexsort(data)\n",
    "    for i in range(len(data)):\n",
    "        while len(hull) > 1 and cross(data[hull[-2]], data[hull[-1]], data[i]) < 0:\n",
    "            hull.pop()\n",
    "        hull.append(i)\n",
    "    for i in reversed(range(len(data))):\n",
    "        while len(hull) > 1 and cross(data[hull[-2]], data[hull[-1]], data[i]) < 0:\n",
    "            hull.pop()\n",
    "        hull.append(i)\n",
    "\n",
    "    return data[list(set(hull))]\n",
    "\n",
    "class Solution:\n",
    "    def outerTrees(self, trees):\n",
    "        trees.sort()\n",
    "        return convex(numpy.array(trees)).tolist()\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
